Colouring graphs whose chromatic number is almost their maximum degree (Q3839005)

As we know, determining if a graph \(G\) with maximum degree \(\Delta\) has a coloring using \(k=\lfloor\Delta-\sqrt \Delta+1\rfloor\) colors is NP-complete provided \(k\geq 3\). In this paper two companion results for graphs whose chromatic number \(\chi(G)\) is close to \(\Delta\) are presented. The first one claims the following: There is a positive \(\varepsilon\) such that for each fixed \(\Delta\) and each \(k\) between \(\Delta+1-\varepsilon\sqrt\Delta\) and \(\Delta+1\), we can determine if \(\chi(G)=k\) in polynomial time. Furthermore, if \(\chi\) is between these two bounds then one can find an optimal coloring in polynomial time. The second is as follows: There is a positive \(\varepsilon\) such that for any \(G\) and each \(k\) between \(\Delta+1-\varepsilon\log\Delta\) and \(\Delta+1\) we can determine if \(\chi(G)=k\) in polynomial time. Furthermore, there is a randomized algorithm to find an optimal coloring with polynomial expected running time on all inputs whose chromatic number lies between these two bounds. In this way the authors point out that the complexity boundary between P and NP-complete coloring problems is (approximately) at \(\Delta-\sqrt\Delta\). For the entire collection see [Zbl 0889.00032].