Perfect graphs of arbitrarily large clique-chromatic number

DOI10.1016/J.JCTB.2015.09.008zbMath1327.05130arXiv1506.08628OpenAlexW1750559240MaRDI QIDQ896010

Pierre Charbit, Nicolas Trotignon, Steéphan Thomassé, Irena Penev

Publication date: 11 December 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.08628

zbMATH Keywords

perfect graphclique coloringclique-chromatic number

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 (17)

Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ Tight bounds on the clique chromatic number ⋮ Structural parameterizations of clique coloring ⋮ 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 ⋮ New bounds on clique-chromatic numbers of Johnson graphs ⋮ Random perfect graphs ⋮ Clique colourings of geometric graphs ⋮ Clique coloring \(B_1\)-EPG graphs ⋮ Unnamed Item ⋮ Lower bounds on the clique-chromatic numbers of some distance graphs ⋮ A linear-time algorithm for clique-coloring planar graphs ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly ⋮ On the complexity of local-equitable coloring of graphs ⋮ A generalization of Grötzsch Theorem on the local-equitable coloring

Cites Work

• Unnamed Item
• Clique-transversal sets of line graphs and complements of line graphs
• 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
• Decomposing and Clique‐Coloring (Diamond, Odd‐Hole)‐Free Graphs
• Sur le coloriage des graphs

This page was built for publication: Perfect graphs of arbitrarily large clique-chromatic number