Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences

DOI10.1016/j.jctb.2008.12.005zbMath1218.05160OpenAlexW2026183431WikidataQ57949597 ScholiaQ57949597MaRDI QIDQ1026014

Kristina Vušković, Ton Kloks, Haiko Müller

Publication date: 23 June 2009

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/74350/2/diamond.pdf

zbMATH Keywords

decompositiongreedy coloring algorithmeven-hole-free graphs\(\beta \)-perfect graphs\(\chi \)-bounded families

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

Vizing bound for the chromatic number on some graph classes ⋮ Colouring diamond-free graphs ⋮ Hereditary Efficiently Dominatable Graphs ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Finding a shortest even hole in polynomial time ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ Weight choosability of graphs with maximum degree 4 ⋮ Graphs of separability at most 2 ⋮ On the structure of (pan, even hole)‐free graphs ⋮ On the forbidden induced subgraph sandwich problem ⋮ A note on chromatic number of (cap, even hole)-free graphs ⋮ Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ On the structure of (even hole, kite)-free graphs ⋮ Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes ⋮ Strong cliques in diamond-free graphs ⋮ Combinatorial optimization with 2-joins ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Triangulated neighborhoods in even-hole-free graphs
• Bisimplicial vertices in even-hole-free graphs
• The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
• On diameters and radii of bridged graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• A class of \(\beta\)-perfect graphs
• Vertex colouring and forbidden subgraphs -- a survey
• \(\beta\)-perfect graphs
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• Graph Theory and Probability
• Even and odd holes in cap-free graphs
• Conditions for β-perfectness
• Characterizations of derived graphs

This page was built for publication: Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences