On the complexity of bicoloring clique hypergraphs of graphs

DOI10.1016/S0196-6774(02)00221-3zbMath1030.68066MaRDI QIDQ4806592

Jan Kratochvíl, Zsolt Tuza

Publication date: 14 May 2003

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

clique hypergraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (37)

Clique-coloring of \(K_{3,3}\)-minor free graphs ⋮ Structural parameterizations of clique coloring ⋮ Positive Semidefinite Zero Forcing: Complexity and Lower Bounds ⋮ Clique-coloring claw-free graphs ⋮ Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 ⋮ On Making Directed Graphs Transitive ⋮ Equitable clique-coloring in claw-free graphs with maximum degree at most 4 ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Tight asymptotics of clique‐chromatic numbers of dense random graphs ⋮ The jump of the clique chromatic number of random graphs ⋮ Clique-coloring UE and UEH graphs ⋮ On star and biclique edge-colorings ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ The chain graph sandwich problem ⋮ Restricted coloring problems on graphs with few \(P_4\)'s ⋮ 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\) ⋮ Clique coloring \(B_1\)-EPG graphs ⋮ Lower bounds for positive semidefinite zero forcing and their applications ⋮ A linear-time algorithm for clique-coloring problem in circular-arc graphs ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ Complexity of clique coloring and related problems ⋮ Balanced vertex-orderings of graphs ⋮ Unnamed Item ⋮ A linear-time algorithm for clique-coloring planar graphs ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ Complexity of clique-coloring odd-hole-free graphs ⋮ Limit theory of combinatorial optimization for random geometric graphs ⋮ Clique-Coloring Circular-Arc 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

This page was built for publication: On the complexity of bicoloring clique hypergraphs of graphs