Colouring Graphs whose Chromatic Number is Almost Their Maimum Degree

摘要

We present efficient algorithms for determining if the chromatic number of an input graph is close to delta. Our results are obtained via the probabilistic method.