On the clique number of the square of a line graph and its relation to maximum degree of the line graph |
| |
| Authors: | Maxime Faron Luke Postle |
| |
| Institution: | 1. Department of Computer Science, Ecole Normale Superieure de Lyon, Lyon, France;2. Canada Research Chair in Graph Theory, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada |
| |
| Abstract: | In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph  , that is,  , can be colored with  colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is,  , is at most  . In 2015, Śleszyńska-Nowak proved that  . In this paper, we prove that  . This theorem follows from our stronger result that  where  . |
| |
| Keywords: | clique number square of a line graph |
|
|
