Coloring the Maximal Cliques of Graphs

DOI10.1137/S0895480199359995zbMath1056.05049OpenAlexW1987622756MaRDI QIDQ4652597

Gábor Bacsó, András Sebő, András Gyárfás, Sylvain Gravier, Myriam Preissmann

Publication date: 28 February 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480199359995

zbMATH Keywords

hypergraphNP-completenesschromatic numberperfect graphpolynomial algorithmsdomination numberclique-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items (44)

Tight bounds on the clique chromatic number ⋮ Clique-coloring of \(K_{3,3}\)-minor free graphs ⋮ Structural parameterizations of clique coloring ⋮ Clique-coloring claw-free graphs ⋮ Subgraph transversal of 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 ⋮ Coloring the cliques of line graphs ⋮ More Results on Clique-chromatic Numbers of Graphs with No Long Path ⋮ 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 ⋮ New bounds on clique-chromatic numbers of Johnson graphs ⋮ Perfect graphs of arbitrarily large clique-chromatic number ⋮ A combinatorial game over biclique-hypergraphs of powers of paths and of powers of cycles through monochromatic transversals ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ Random perfect graphs ⋮ 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 ⋮ A linear-time algorithm for clique-coloring problem in circular-arc graphs ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ Claw-free cubic graphs with clique-transversal number half of their order ⋮ Complexity of clique coloring and related problems ⋮ Unnamed Item ⋮ Graphs with large clique-chromatic numbers ⋮ Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable ⋮ Lower bounds on the clique-chromatic numbers of some distance graphs ⋮ A linear-time algorithm for clique-coloring planar graphs ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ Algorithms for unipolar and generalized split graphs ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly ⋮ Clique chromatic numbers of intersection graphs ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ Complexity of clique-coloring odd-hole-free 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: Coloring the Maximal Cliques of Graphs