Complexity of clique coloring and related problems

DOI10.1016/j.tcs.2011.02.038zbMath1222.05070OpenAlexW2026705714MaRDI QIDQ551168

Dániel Marx

Publication date: 14 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.02.038

zbMATH Keywords

complexitypolynomial hierarchychoosabilityclique coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Structural parameterizations of clique coloring ⋮ 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 ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ The jump of the clique chromatic number of random graphs ⋮ On star and biclique edge-colorings ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ Clique colourings of geometric graphs ⋮ Biclique-colouring verification complexity and biclique-colouring power graphs ⋮ Subgraph-avoiding coloring of 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 ⋮ Unnamed Item ⋮ Complexity of secure sets ⋮ A linear-time algorithm for clique-coloring planar graphs ⋮ The trouble with the second quantifier ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly ⋮ Complexity of Secure Sets ⋮ Complexity of clique-coloring odd-hole-free graphs ⋮ On the complexity of local-equitable coloring of graphs ⋮ The clique-perfectness and clique-coloring of outer-planar graphs ⋮ A generalization of Grötzsch Theorem on the local-equitable coloring ⋮ Hitting all maximal independent sets of a bipartite graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of planar graph choosability
• Two-colouring all two-element maximal antichains
• The Grötzsch theorem for the hypergraph of maximal cliques
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Clique-coloring some classes of odd-hole-free graphs
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• On the divisibility of graphs

This page was built for publication: Complexity of clique coloring and related problems