On the clique number of the square of a line graph and its relation to Ore-degree

Maxime Faron, Luke Postle

In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph $G$, that is $L(G{)}^2$, can be colored with $\frac{5}{4}\Delta (G{)}^2$ colors. This conjecture implies…