Problem #149: Let $G$ be a graph with maximum degree $\Delta$

---

Progress

Asked by Erdős and Nešetřil in 1985 (see [FGST89]). This is equivalent to asking whether the chromatic number of the square of the line graph $L(G)^2$ is at most $\frac{5}{4}\Delta^2$.

This bound would be the best possible, as witnessed by a blowup of $C_5$. The minimum number of such sets required is sometimes called the strong chromatic index of $G$.

The weaker conjecture that there exists some $c>0$ such that $(2-c)\Delta^2$ sets suffice was proved by Molloy and Reed [MoRe97], who proved that $1.998\Delta^2$ sets suffice (for $\Delta$ sufficiently large). This was improved to $1.93\Delta^2$ by Bruhn and Joos [BrJo18] and to $1.835\Delta^2$ by Bonamy, Perrett, and Postle [BPP22]. The best bound currently available is\[1.772\Delta^2,\]proved by Hurley, de Joannis de Verclos, and Kang [HJK22]. Mahdian has, in their Masters' thesis, proved an upper bound of $(2+o(1))\frac{\Delta^2}{\log \Delta}$ under the additional assumption that $G$ is $C_4$-free.

Erdős and Nešetřil also asked the easier problem of whether $G$ containing at least $\tfrac{5}{4}\Delta^2$ many edges implies $G$ containing two strongly independent edges. This was proved by Chung, Gyárfás, Tuza, and Trotter [CGTT90].

It is still open even whether the clique number of $L(G)^2$ at most $\frac{5}{4}\Delta^2$. Let $\omega=\omega(L(G)^2)$ be this clique number. Śleszyńska-Nowak [Sl15] proved $\omega \leq \frac{3}{2}\Delta^2$. Faron and Postle [FaPo19] proved $\omega\leq \frac{4}{3}\Delta^2$. Cames van Batenburg, Kang, and Pirot [CKP20] have proved $\omega\leq \frac{5}{4}\Delta^2$ under the additional assumption that $G$ is triangle-free (and $\omega\leq \Delta^2$ if $G$ is $C_5$-free).