Colouring Gn,p and Spectral Techniques
Lars Kuhtz
In consideration of the NP-hardness of the graph colouring problem Karp asked in 1984 if there is an algorithm that colours a graph optimally in expected polynomial time thus directing the focus from the worst case complexity to the average case setting. For the Gn,p model Krivelevich and Vu in 2002 presented an algorithm that, for relatively dense graphs, approximates the chromatic number within a ratio of O((np)1/2/ln(np)) in expected polynomial time. They asked if a similar result holds for sparse graphs, too. This was recently proved by Coja-Oghlan, Moore, Sanwalani and Taraz, although for a slightly worse approximation ratio. We present a colouring algorithm that, on sparse graphs, has the same approximation ratio as the algorithm of Krivelevich and Vu and has expected polynomial running time over Gn,p. Considering the list-colouring problem, we use the previous result to obtain an algorithm that approximates the choice number of a graph within an approximation ratio of O((np)1/2ln(n)/ln(np)) in expected polynomial time over Gn,p.
In a way, all of the above algorithms use graph properties that are closely related to the eigenvalue spectrum of the adjacency matrix of the input graph. Hence, in an average case setting, the distribution of the eigenvalues of the adjacency matrix of a random graph attain special attention. We improve a result of Feige and Ofek from 2003 concerning the second eigenvalue of the adjacency matrix of Gn,p.
Diploma Thesis.