Colouring graphs with sparse neighbourhoods: bounds and applications (Q2131867)

\textit{B. Reed}'s conjecture [J. Graph Theory 27, No. 4, 177--212 (1998; Zbl 0980.05026)] states that \(\chi\leq \lceil (1-\varepsilon)(\Delta+1)+\varepsilon \omega \rceil\) for every \(\varepsilon\leq 1/2\), where \(\chi\) denotes the chromatic number of a graph, \(\Delta\) its maximum degree and \(\omega\) the clique number. The main result of the paper is the improvement in the value of \(\varepsilon\) -- the previous \(\varepsilon\leq 1/130,000\) has been improved to \(\varepsilon \leq 1/26\). To prove it the authors use a technique that allows to bound from above the chromatic number of a graph where every vertex has little edges in its neighborhood. In particular they show that if a graph is \(L\)-critical with respect to some list assignment \(L\) (that is it is not \(L\)-colorable but its every proper subgraph is) then it must be \(\delta\)-sparse for some reasonable value of \(\delta\) (that is, every neighborhood induces at most \((1-\delta)\binom{\Delta}{2}\) edges). They also prove an upper bound on the list coloring number depending on \(\Delta\) and \(\delta\). These two results allow to prove the above mentioned fact that \(\chi\leq \lceil 25/26(\Delta+1)+1/26 \omega \rceil\) for all the graphs with \(\Delta>\Delta_0\), where \(\Delta_0\) is some absolute constant. These results allowed to improve the bounds on the strong chromatic index \(\chi_s\) (that is the least integer allowing a coloring in which the edges at distance at most \(2\) have distinct colors). Erdős and Nešetřil conjectured that \(\chi^\prime_s\leq 1.25\Delta^2\) for every graph \(G\). The best result so far was \(\chi^\prime_s\leq 1.93\Delta^2\), the authors applied their techniques to strengthen it to \(\chi^\prime_s\leq 1.835\Delta^2\).