Journal of Combinatorics

Volume 1 (2010)

Number 4

Increasing the chromatic number of a random graph

Pages: 345 – 356



Noga Alon (Schools of Mathematics and Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel)

Benny Sudakov (Department of Mathematics, University of California at Los Angeles)


What is the minimum number of edges that have to be added to therandom graph $G=G_{n,0.5}$ in order to increase its chromatic number$\chi=\chi(G)$ by one percent? One possibility is to add allmissing edges on a set of $1.01 \chi$ vertices, thuscreating a clique of chromatic number $1.01 \chi$.This requires, with high probability,the addition of $\Omega(n^2/\log^2 n)$ edges.We show that this is tight up to a constant factor, consider thequestion 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 graphproperties, initiated by the second author and Vu, and improvesone of their results.

Full Text (PDF format)