An improved procedure for colouring graphs of bounded local density

Eoin Hurley ; Rémi de Joannis de Verclos ; Ross J. Kang

Advances in Combinatronics (2022)

Résumé

We develop an improved bound for the chromatic number of graphs of maximum degree $\Delta$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-\sigma)\binom{\Delta}{2}$ for some fixed $0\sigma1$. The leading term in the reduction of colours achieved through this bound is best possible as $\sigma\to0$. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erd\H{o}s-Ne\v{s}et\v{r}il conjecture and Reed's conjecture. We prove that the strong chromatic index is at most $1.772\Delta^2$ for any graph $G$ with sufficiently large maximum degree $\Delta$. We prove that the chromatic number is at most $\lceil 0.881(\Delta+1)+0.119\omega\rceil$ for any graph $G$ with clique number $\omega$ and sufficiently large maximum degree $\Delta$. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most $(1-\sigma)\Delta$, and establish what may be considered first progress towards a conjecture of Vu.

Détail

Publié le : 2022-09-22