Increasing the chromatic number of a random graph

N. Alon, B. Sudakov

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 $\chi =\chi (G)$ by one percent ? One possibility is t…