Complexity of clique coloring and related problems
From MaRDI portal
Publication:551168
DOI10.1016/j.tcs.2011.02.038zbMath1222.05070MaRDI QIDQ551168
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
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
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, Clique colourings of geometric graphs, Complexity of secure sets, Complexity-separating graph classes for vertex, edge and total colouring, A linear-time algorithm for clique-coloring planar graphs, List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly, The clique-perfectness and clique-coloring of outer-planar graphs, Hitting all maximal independent sets of a bipartite graph, Clique-transversal sets and clique-coloring in planar 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, Complexity of Secure Sets, On star and biclique edge-colorings, Subgraph-avoiding coloring of graphs, Complexity of clique-coloring odd-hole-free graphs
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
