Tree-width dichotomy. (English) Zbl 1487.05221
Summary: 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.
MSC:
| 05C75 | Structural characterization of families of graphs |
| 05C12 | Distance in graphs |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05D10 | Ramsey theory |
Keywords:
minimal forbidden induced subgraphs for individual hereditary classes; family of hereditary classesReferences:
| [1] | Bodlaender, H. L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148 |
| [2] | Bodlaender, H. L.; Thilikos, D. M., Treewidth for graphs with small chordality, Discrete Appl. Math., 79, 45-61 (1997) · Zbl 0895.68113 |
| [3] | Reed, B., (Treewidth and Tangles: A New Connectivity Measure and Some Applications. Treewidth and Tangles: A New Connectivity Measure and Some Applications, London Math. Soc. Lecture Note Ser., vol. 241 (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 87-162 · Zbl 0895.05034 |
| [4] | Robertson, N.; Seymour, P. D., Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, 92, 325-357 (2004) · Zbl 1061.05088 |
| [5] | Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41, 92-114 (1986) · Zbl 0598.05055 |
| [6] | Alekseev, V. E., On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math., 132, 17-26 (2003) · Zbl 1029.05140 |
| [7] | Erdős, P., Graph theory and probability, Canad. J. Math., 11, 34-38 (1959) · Zbl 0084.39602 |
| [8] | Chudnovsky, M.; Seymour, P., Extending the Gyárfás-Sumner conjecture, J. Combin. Theory Ser. B, 105, 11-16 (2014) · Zbl 1300.05168 |
| [9] | Weißauer, D., On the block number of graphs, SIAM J. Discrete Math., 33, 346-357 (2019) · Zbl 1405.05091 |
| [10] | Lozin, V., Boundary classes of planar graphs, Combin. Probab. Comput., 17, 287-295 (2008) · Zbl 1166.05016 |
| [11] | Lozin, V.; Rautenbach, D., On the band-, tree-, and clique-width of graphs with bounded vertex degree, SIAM J. Discrete Math., 18, 195-206 (2004) · Zbl 1081.05098 |
| [12] | D. Weißauer, In absence of long chordless cycles, large tree-width becomes a local phenomenon, J. Combin. Theory Ser. B 139 (2019) 342-352. · Zbl 1428.05122 |
| [13] | Kühn, D.; Osthus, D., Induced subdivisions in \(K_{s , s}\)-free graphs of large average degree, Combinatorica, 24, 287-304 (2004) · Zbl 1056.05082 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
