Perfect graphs of arbitrarily large clique-chromatic number

DOI10.1016/J.JCTB.2015.09.008zbMATH Open1327.05130arXiv1506.08628OpenAlexW1750559240MaRDI QIDQ896010FDOQ896010

Authors: Pierre Charbit, Irena Penev, Stéphan Thomassé, Nicolas Trotignon 

Publication date: 11 December 2015

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

Abstract: We prove that there exist perfect graphs of arbitrarily large clique-chromatic number. These graphs can be obtained from cobipartite graphs by repeatedly gluing along cliques. This negatively answers a question raised by Duffus, Sands, Sauer, and Woodrow in [Two-coloring all two-element maximal antichains, J. Combinatorial Theory, Ser. A, 57 (1991), 109-116].

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

Recommendations

• Graphs with large clique-chromatic numbers
• Coloring the Maximal Cliques of Graphs
• scientific article
• A note on perfect graphs
• Perfect graphs with no balanced skew-partition are 2-clique-colorable

zbMATH Keywords

perfect graphclique coloringclique-chromatic number

Mathematics Subject Classification ID

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

Cites Work

• Sur le coloriage des graphs
• Title not available (Why is that?)
• Clique-transversal sets of line graphs and complements of line graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• The Grötzsch theorem for the hypergraph of maximal cliques
• Coloring the Maximal Cliques of Graphs
• Two-colouring all two-element maximal antichains
• Clique-coloring some classes of odd-hole-free graphs
• Decomposing and clique-coloring (diamond, odd-hole)-free graphs

Cited In (18)

• Tight bounds on the clique chromatic number
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• A linear-time algorithm for clique-coloring planar graphs
• List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly
• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• Discrepancy and sparsity
• Equitable clique-coloring in claw-free graphs with maximum degree at most 4
• New bounds on clique-chromatic numbers of Johnson graphs
• Lower bounds on the clique-chromatic numbers of some distance graphs
• Random perfect graphs
• Title not available (Why is that?)
• The jump of the clique chromatic number of random graphs
• Complexity-separating graph classes for vertex, edge and total colouring
• Structural parameterizations of clique coloring
• On the complexity of local-equitable coloring of graphs
• Clique coloring \(B_1\)-EPG graphs
• Clique colourings of geometric graphs
• A generalization of Grötzsch Theorem on the local-equitable coloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896010)