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

Abstract: In 1985, ErdH{o}s and Nev{s}etv{r}il conjectured that the square of the line graph of a graph

G

, that is

L (G)^{2}

, can be colored with

f r a c 54 D e l t a (G)^{2}

colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is

o m e g a (L (G)^{2})

, is at most

f r a c 54 D e l t a (G)^{2}

. In 2015, 'Sleszy'nska-Nowak proved that

o m e g a (L (G)^{2}) l e f r a c 32 D e l t a (G)^{2}

. In this paper, we prove that

o m e g a (L (G)^{2}) l e f r a c 43 D e l t a (G)^{2}

. This theorem follows from our stronger result that

o m e g a (L (G)^{2}) l e f r a c s i g m a (G)^{2} 3

where

s i g m a (G) := m a x_{u v i n E (G)} d (u) + d (v)

, is the Ore-degree of the graph

G

.

This page was built for publication: On the clique number of the square of a line graph and its relation to Ore-degree