Perfect graphs of arbitrarily large clique-chromatic number

DOI10.1016/J.JCTB.2015.09.008MaRDI QIDQ896010zbMATHOpenAlexFDO

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)

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

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)

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].

Recommendations

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

Cites work

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

Cited in

(18)

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

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)