On the Chromatic Number of the Complement of a Class of Line Graphs

Abstract

Let \(G\) be a graph, \(\overline{G}\) its complement, \(L(G)\) its line graph, and \(\chi(G)\) its chromatic number. Then we have the following

THEOREM Let \(G\) be a graph with \(n\) vertices. (i) If \(G\) is triangle
free, then

\[n-4 \leq \chi\left(\overline{L(\overline{G})}\right)\leq n-2\]

(ii) If G is planar and every triangle bounds a disk, then

\[n-3 \leq \chi\left(\overline{L(\overline{G})}\right)\leq n-2\]