Tree-width dichotomy

DOI10.1016/J.EJC.2022.103517zbMATH Open1487.05221arXiv2012.01115OpenAlexW4213145937MaRDI QIDQ2136198FDOQ2136198

Igor Razgon, Vadim Lozin

Publication date: 10 May 2022

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

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.

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)

Cites Work

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

Cited In (15)

• 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
• Product structure of graph classes with bounded treewidth
• Hereditary classes of graphs: a parametric approach
• Induced subgraphs and path decompositions
• On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• Bounding branch-width
• Treewidth, Circle Graphs, and Circular Drawings
• Computational complexity aspects of super domination
• Treewidth, circle graphs and circular drawings
• Induced subdivisions with pinned branch vertices
• Title not available (Why is that?)
• 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)