Tree-width dichotomy

DOI10.1016/J.EJC.2022.103517MaRDI QIDQ2136198zbMATHOpenAlexFDO

Authors Vadim Lozin, Igor Razgon

Publication date 10 May 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.01115

zbMATH Keywords

family of hereditary classesminimal forbidden induced subgraphs for individual hereditary classes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Structural characterization of families of graphs (05C75) Ramsey theory (05D10)

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.

Recommendations

• scientific article; zbMATH DE number 1696534
• scientific article; zbMATH DE number 772777
• scientific article; zbMATH DE number 4210186
• scientific article; zbMATH DE number 1979486
• The tree- and clique-width of bipartite graphs in special classes

Cites work

• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Boundary Classes of Planar Graphs
• Extending the Gyárfás-Sumner conjecture
• Graph Theory and Probability
• Graph minors. V. Excluding a planar graph
• Graph minors. XX: Wagner's conjecture
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the block number of graphs
• Treewidth for graphs with small chordality

Cited in

(15)

• Induced subdivisions with pinned branch vertices
• Domino Treewidth
• Hereditary classes of graphs: a parametric approach
• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree
• Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
• scientific article; zbMATH DE number 3957503 (Why is no real title available?)
• On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
• Induced subgraphs and path decompositions
• Separating layered treewidth and row treewidth
• Treewidth, Circle Graphs, and Circular Drawings
• Product structure of graph classes with bounded treewidth
• Bounding branch-width
• Computational complexity aspects of super domination
• Treewidth, circle graphs and circular drawings

This page was built for publication: Tree-width dichotomy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136198)