Complexity of clique-coloring odd-hole-free graphs
From MaRDI portal
Publication:3652547
DOI10.1002/jgt.20387zbMath1182.05092OpenAlexW4251123531MaRDI QIDQ3652547
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
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
