Increasing the chromatic number of a random graph

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)

Published 1 January 2010