On the tree-width of even-hole-free graphs

DOI10.1016/J.EJC.2021.103394MaRDI QIDQ1979431zbMATH OpenOpenAlexFDO

Authors Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon

Publication date 2 September 2021

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

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

zbMATH Keywords

contraction of subgraphsgraph minorstree-width

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Abstract: The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, $K_4$)-free graphs was constructed, that still has unbounded tree-width [Sintiari and Trotignon, 2019]. The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary. We prove that for every graph $G$, if $G$ excludes a fixed graph $H$ as a minor, then $G$ either has small tree-width, or $G$ contains a large wall or the line graph of a large wall as induced subgraph. This can be seen as a strengthening of Robertson and Seymour's excluded grid theorem for the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a more general class: (theta, prism)-free graphs. This implies the known result that planar even hole-free graph have bounded tree-width [da Silva and Linhares Sales, Discrete Applied Mathematics 2010]. We conjecture that even-hole-free graphs of bounded degree have bounded tree-width. If true, this would mean that even-hole-freeness is testable in the bounded-degree graph model of property testing. We prove the conjecture for subcubic graphs and we give a bound on the tree-width of the class of (even hole, pyramid)-free graphs of degree at most 4.

Recommendations

• Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
• A bound on the treewidth of planar even-hole-free graphs
• Even-hole-free planar graphs have bounded treewidth
• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

Cites work

• A bound on the treewidth of planar even-hole-free graphs
• Clique-cutsets beyond chordal graphs
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• Contraction obstructions for treewidth
• Even-hole-free graphs: A survey
• Every minor-closed property of sparse graphs is testable
• Every property of hyperfinite graphs is testable
• Graph minors. V. Excluding a planar graph
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 3520445 (Why is no real title available?)
• Introduction to Property Testing
• Local Graph Partitions for Approximation and Testing
• On finite Ramsey numbers
• On the structure of (pan, even hole)-free graphs
• Property testing for bounded degree databases
• Property testing in bounded degree graphs
• Property testing on \(k\)-vertex-connectivity of graphs
• Random walks and forbidden minors II
• Structure and algorithms for (cap, even hole)-free graphs
• Testing subdivision-freeness: property testing meets structural graph theory
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth for graphs with small chordality

Cited in

(27)

• Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
• Grid induced minor theorem for graphs of small degree
• Even-hole-free graphs. I: Decomposition theorem
• Even-hole-free planar graphs have bounded treewidth
• On rank-width of (diamond, even-hole)-free graphs
• Even-hole-free graphs: A survey
• On the parameterized complexity of the acyclic matching problem
• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
• Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
• 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
• Induced subgraphs and path decompositions
• Treewidth, Circle Graphs, and Circular Drawings
• Induced subgraphs and tree decompositions V. one neighbor in a hole
• On the treewidth of Hanoi graphs
• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• Treewidth, circle graphs and circular drawings
• On the size of two minimal linkages
• Induced subgraphs and tree decompositions. XVI: Complete bipartite induced minors
• Twin-width of subdivisions of multigraphs
• Sparse induced subgraphs of large treewidth
• Induced subgraphs and tree decompositions. XII: Grid theorem for pinched graphs
• Rank-width and tree-width of \(H\)-minor-free graphs
• Sparse outerstring graphs have logarithmic treewidth
• Induced subgraphs and tree decompositions XIX: thetas and forests
• A simple layered-wheel-like construction
• A bound on the treewidth of planar even-hole-free graphs

This page was built for publication: On the tree-width of even-hole-free graphs

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