Increasing the chromatic number of a random graph

2010/02/09 by Noga Alon, Benny Sudakov, Alon, N. +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1002.1748

openalex publication_date 2010/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

What is the minimum number of edges that have to be added to the random graph G=G_n,0.5 in order to increase its chromatic number χ=χ(G) by one percent ? One possibility is to add all missing edges on a set of 1.01 χ vertices, thus creating a clique of chromatic number 1.01 χ. This requires, with high probability, the addition of Ω(n²/log² n) edges. We show that this is tight up to a constant factor, consider the question for more general random graphs G_n,p with p=p(n), and study a local version of the question as well. The question is motivated by the study of the resilience of graph properties, initiated by the second author and Vu, and improves one of their results.

Cited by

• Colour-biased Hamilton cycles in dense graphs and random graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• Asymptotic Normality of the Chromatic Number of a Random Graph

Related

• The clique chromatic number of sparse random graphs
• Tight asymptotics of clique-chromatic numbers of dense random graphs
• Clique colouring of binomial random graphs
• The oriented chromatic number of random graphs of bounded degree
• Clique coloring of dense random graphs