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

DOI10.1016/j.ejc.2021.103394zbMath1471.05090arXiv2008.05504OpenAlexW3195643205MaRDI QIDQ1979431

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

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

tree-widthgraph minorscontraction of subgraphs

Mathematics Subject Classification ID

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

Related Items

Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree, On the parameterized complexity of the acyclic matching problem, 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, Grid induced minor theorem for graphs of small degree

Cites Work

• Unnamed Item
• Unnamed Item
• Every minor-closed property of sparse graphs is testable
• A bound on the treewidth of planar even-hole-free graphs
• Graph minors. V. Excluding a planar graph
• On finite Ramsey numbers
• Treewidth for graphs with small chordality
• Structure and algorithms for (cap, even hole)-free graphs
• Contraction obstructions for treewidth
• Property testing on \(k\)-vertex-connectivity of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Every Property of Hyperfinite Graphs Is Testable
• Property Testing for Bounded Degree Databases
• On the structure of (pan, even hole)‐free graphs
• Even-hole-free graphs: A survey
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• Local Graph Partitions for Approximation and Testing
• Random walks and forbidden minors II
• Introduction to Property Testing
• Clique‐cutsets beyond chordal graphs
• Testing subdivision-freeness
• Property testing in bounded degree graphs