The jump of the clique chromatic number of random graphs

DOI10.1002/rsa.21128zbMath1525.05050arXiv2105.12168OpenAlexW3164101730MaRDI QIDQ6076219

Lutz Warnke, Dieter Mitsche, Lyuben Lichev

Publication date: 23 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionrandom graphcritical windowclique chromatic number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

On the concentration of the chromatic number of random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of clique coloring and related problems
• Clique-transversal sets of line graphs and complements of line graphs
• Tight bounds on the clique chromatic number
• Perfect graphs of arbitrarily large clique-chromatic number
• Two-colouring all two-element maximal antichains
• The Grötzsch theorem for the hypergraph of maximal cliques
• On the missing log in upper tail estimates
• Upper tail bounds for stars
• Graph Theory and Probability. II
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• The Janson inequalities for general up‐sets
• Clique coloring of binomial random graphs
• On the Method of Typical Bounded Differences
• When does the K₄‐free process stop?