Tight bounds on the clique chromatic number

DOI10.37236/9659MaRDI QIDQ820840zbMATH OpenOpenAlexFDO

Authors Gwenaël Joret, Piotr Micek, Bruce Reed, Michiel Smid

Publication date 28 September 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

clique colouringperfect graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Review text

Summary: The clique chromatic number of a graph is the minimum number of colours needed to colour its vertices so that no inclusion-wise maximal clique which is not an isolated vertex is monochromatic. We show that every graph of maximum degree \(\Delta\) has clique chromatic number \(O\left(\frac{\Delta}{\log\Delta}\right)\). We obtain as a corollary that every \(n\)-vertex graph has clique chromatic number \(O\left(\sqrt{\frac{n}{\log n}}\right)\). Both these results are tight.

Recommendations

• Clique coloring of dense random graphs
• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• Clique coloring of binomial random graphs
• More results on clique-chromatic numbers of graphs with no long path
• New bounds on clique-chromatic numbers of Johnson graphs

Cites work

• Clique coloring of binomial random graphs
• Coloring the Maximal Cliques of Graphs
• Fibres and ordered set coloring
• On the divisibility of graphs
• Perfect graphs of arbitrarily large clique-chromatic number
• The Grötzsch theorem for the hypergraph of maximal cliques
• The list chromatic number of graphs with small clique number
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Two-colouring all two-element maximal antichains
• Unsolved graph colouring problems

Cited in

(18)

• New bounds on clique-chromatic numbers of Johnson graphs
• New bounds for the clique-chromatic numbers of Johnson graphs
• Chromatic number versus chromatic number in graphs with bounded clique number
• Graphs with large clique-chromatic numbers
• A tight bound on the set chromatic number
• A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs
• More results on clique-chromatic numbers of graphs with no long path
• On Cliques and Clique Chromatic Numbers in Line, Lict and Lictact Graphs
• On graphs with linear Ramsey numbers
• Clique coloring of dense random graphs
• scientific article; zbMATH DE number 7024788 (Why is no real title available?)
• Clique coloring of binomial random graphs
• Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques
• Coloring Graphs with Dense Neighborhoods
• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• The jump of the clique chromatic number of random graphs
• Tight Bounds on the Clique Chromatic Number
• The clique chromatic number of sparse random graphs

This page was built for publication: Tight bounds on the clique chromatic number

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