Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs

DOI10.37236/11623zbMath1517.05121arXiv2203.06775OpenAlexW4380990053MaRDI QIDQ6106299

Tara Abrishami, Sepehr Hajebi, Maria Chudnovsky, Sophie Spirkl

Publication date: 27 June 2023

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

decompositioncombinatorial optimizationtreewidthcoloringmaximum weight stable setclique-widthstructure theoremeven-hole-free graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Induced subgraphs and tree decompositions V. one neighbor in a hole

Cites Work

• Unnamed Item
• On graphs with no induced subdivision of \(K_4\)
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Safe separators for treewidth
• Graph minors. V. Excluding a planar graph
• Structure and algorithms for (cap, even hole)-free graphs
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• On the tree-width of even-hole-free graphs
• Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
• Grid induced minor theorem for graphs of small degree
• Parameters Tied to Treewidth
• Parameterized Algorithms
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

This page was built for publication: Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs