Complexity of clique-coloring odd-hole-free graphs

DOI10.1002/jgt.20387zbMath1182.05092OpenAlexW4251123531MaRDI QIDQ3652547

David Défossez

Publication date: 18 December 2009

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20387

zbMATH Keywords

holeodd-hole-free graphsclique-coloringclique chromatic numberco-diamondco-diamond free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (17)

Clique-coloring of \(K_{3,3}\)-minor free graphs ⋮ Clique-coloring claw-free graphs ⋮ Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 ⋮ Equitable clique-coloring in claw-free graphs with maximum degree at most 4 ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ Biclique-colouring verification complexity and biclique-colouring power graphs ⋮ Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\) ⋮ A linear-time algorithm for clique-coloring problem in circular-arc graphs ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable ⋮ A linear-time algorithm for clique-coloring planar graphs ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ On the complexity of local-equitable coloring of graphs ⋮ The clique-perfectness and clique-coloring of outer-planar graphs ⋮ A faster algorithm to recognize even-hole-free graphs ⋮ A generalization of Grötzsch Theorem on the local-equitable coloring

Cites Work

• Unnamed Item
• Complexity of clique coloring and related problems
• The strong perfect graph theorem
• Bull-free Berge graphs are perfect
• Recognizing claw-free perfect graphs
• Two-colouring all two-element maximal antichains
• Fibres and ordered set coloring
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Recognizing bull-free perfect graphs
• Recognizing Berge graphs
• Clique-coloring some classes of odd-hole-free graphs
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs

This page was built for publication: Complexity of clique-coloring odd-hole-free graphs