Tree-width dichotomy
Preprint
Abstract
We prove that the tree-width of graphs in a hereditary class defined by a finite set $F$ of forbidden induced subgraphs is bounded if and only if $F$ includes a complete graph, a complete bipartite graph, a tripod (a forest in which every connected component has at most 3 leaves) and the line graph of a tripod.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- In absence of long chordless cycles, large tree-width becomes a local phenomenonJournal of Combinatorial Theory, Series B, 2019
- On the Block Number of GraphsSIAM Journal on Discrete Mathematics, 2019
- Boundary Classes of Planar GraphsCombinatorics, Probability and Computing, 2008
- Graph Minors. XX. Wagner's conjectureJournal of Combinatorial Theory, Series B, 2004
- Induced Subdivisions In K s,s -Free Graphs of Large Average DegreeCombinatorica, 2004
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex DegreeSIAM Journal on Discrete Mathematics, 2004
- On easy and hard hereditary classes of graphs with respect to the independent set problemDiscrete Applied Mathematics, 2003
- Treewidth for graphs with small chordalityDiscrete Applied Mathematics, 1997
- Graph minors. V. Excluding a planar graphJournal of Combinatorial Theory, Series B, 1986
- Graph Theory and ProbabilityCanadian Journal of Mathematics, 1959