Graphs without even holes or diamonds

2011/04/20 by Ton Kloks, Kloks, Ton
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1104.3920

openalex publication_date 2011/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An even hole is an induced chordless cycle of even length at least four. A diamond is an induced subgraph isomorphic to K₄-e. We show that graphs without even holes and without diamonds can be decomposed via clique-separators into graphs that have uniformly bounded cliquewidth.

Related

• Clique Separator Decomposition of Hole- and Diamond-Free Graphs and\n Algorithmic Consequences
• Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graphs of large treewidth
• On the structure of (pan, even hole)-free graphs
• Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
• Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree