ALCOMFT-TR-03-181

Sotiris Nikoletseas and Paul Spirakis
How to certify in deterministic polynomial time the high chromatic number of instances of sparse random graphs
Patras. Work package 4. December 2003.

Abstract: In this work we show how to certify in deterministic polynomial time that an instance G of the random graph G_n,p with p=(c(n))/n (where c(n) << n^\delta, \forall \delta >0 but c(n) -> + \infty as n -> + \infty ) has a high vertex chromatic number.

Our certifier is based on the following fact that we show here: Let the eigenvalues of the adjacency matrix A of G be lambda₁ = lambda_max >= lambda₂ >= ··· >= lambda_n = lambda_min . Let lambda = max_{i=2, ..., n} |lambda_i | and \nu = (lambda₁ )/(lambda) be the eigenvalue gap of G. We show that \nu -> +\infty almost surely in such graphs.

Postscript file: ALCOMFT-TR-03-181.ps.gz (96 kb).