Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
DOI10.1016/J.JCTB.2008.12.005zbMATH Open1218.05160OpenAlexW2026183431WikidataQ57949597 ScholiaQ57949597MaRDI QIDQ1026014FDOQ1026014
Authors: Ton Kloks, Haiko Müller, Kristina Vušković 
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
Recommendations
decompositiongreedy coloring algorithmeven-hole-free graphs\(\beta \)-perfect graphs\(\chi \)-bounded families
Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)
Cites Work
- Graph Theory and Probability
- Title not available (Why is that?)
- Characterizations of derived graphs
- The strong perfect graph theorem
- \(\beta\)-perfect graphs
- On diameters and radii of bridged graphs
- Vertex colouring and forbidden subgraphs -- a survey
- Alpha-balanced graphs and matrices and GF(3)-representability of matroids
- Even pairs
- Even-hole-free graphs. I: Decomposition theorem
- Even and odd holes in cap-free graphs
- Even-hole-free graphs part II: Recognition algorithm
- Bisimplicial vertices in even-hole-free graphs
- Triangulated neighborhoods in even-hole-free graphs
- The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
- A class of \(\beta\)-perfect graphs
- Conditions for β-perfectness
Cited In (36)
- Even-hole-free graphs: A survey
- Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
- Finding a shortest even hole in polynomial time
- Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs
- The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
- On the structure of (banner, odd hole)-free graphs
- Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- On the structure of (even hole, kite)-free graphs
- Graphs of separability at most 2
- Strong cliques in diamond-free graphs
- A proof of Hougardy's conjecture for diamond-free graphs
- Decomposing and clique-coloring (diamond, odd-hole)-free graphs
- Structure and algorithms for (cap, even hole)-free graphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- On the chromatic number of (\(P_6\), diamond)-free graphs
- Triangulated neighborhoods in even-hole-free graphs
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Weight choosability of graphs with maximum degree 4
- Colouring diamond-free graphs
- On rank-width of (diamond, even-hole)-free graphs
- A faster algorithm to recognize even-hole-free graphs
- Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes
- Graphs of separability at most two: structural characterizations and their consequences
- Vizing bound for the chromatic number on some graph classes
- Perfectly contractile diamond-free graphs
- Linear χ -binding functions for some classes of ( P 3 ∪ P 2 )-free graphs
- Even-hole-free graphs. I: Decomposition theorem
- On the forbidden induced subgraph sandwich problem
- Hereditary efficiently dominatable graphs
- On the structure of (pan, even hole)-free graphs
- Combinatorial optimization with 2-joins
- A faster algorithm to recognize even-hole-free graphs
- A note on chromatic number of (cap, even hole)-free graphs
- Even-hole-free graphs part II: Recognition algorithm
- Even-hole-free graphs still have bisimplicial vertices
This page was built for publication: Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1026014)
