Tree-width dichotomy

DOI10.1016/J.EJC.2022.103517MaRDI QIDQ2136198zbMATH OpenOpenAlexFDO

Authors Vadim Lozin, Igor Razgon

Publication date 10 May 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

(24)

• Separating layered treewidth and row treewidth
• 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
• Hereditary classes of graphs: a parametric approach
• Comparing width parameters on graph classes
• Product structure of graph classes with bounded treewidth
• Induced subgraphs and path decompositions
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• Induced subgraphs and tree decompositions. XII: Grid theorem for pinched graphs
• The Hamiltonian cycle problem and monotone classes
• Complexity framework for forbidden subgraphs. I: The framework
• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• Bounding branch-width
• Graph problems and monotone classes
• Treewidth, Circle Graphs, and Circular Drawings
• Computational complexity aspects of super domination
• Treewidth, circle graphs and circular drawings
• Induced subdivisions with pinned branch vertices
• A Ramsey-type theorem on deficiency
• Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs
• Treewidth versus clique number. V: Further connections with tree-independence number
• Max weight independent set in sparse graphs with no long claws
• scientific article; zbMATH DE number 3957503 (Why is no real title available?)
• Domino Treewidth

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)