Paper Info
Title
Independent packings in structured graphs
Abstract
Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs.
Year
DOI
Venue
2006
10.1007/s10107-005-0649-5
Math. Program.
Keywords
Field
DocType
cocomparability graph,dissociation set.,polygon-circle graph,circular-arc graph,weakly chordal graph,interval-filament graph,induced matching,chordal graph,independent set,chordal bipartite graph,asteroidal triple-free graph,intersection graph,outerplanar graph,bipartite graph,polynomial time,connected graph
Discrete mathematics,Indifference graph,Combinatorics,Clique-sum,Chordal graph,Polygon-circle graph,Cograph,Pathwidth,Mathematics,Maximal independent set,Split graph
Journal
Volume
Issue
ISSN
105
2-3
1436-4646
Citations 
PageRank 
References 
20
0.80
39
Authors
2
Name
Order
Citations
PageRank
Kathie Cameron124624.16
Pavol Hell22638288.75