On the Chromatic Number of the Complement of a Class of Line Graphs.
Paul Renteln · 2003
Let G beagraph, G its complement, L(G) its line graph, and χ(G) its chromatic number. Then we have the following Theorem Let G be agraph with n vertices. (i) If G is triangle free, then n − 4 ≤ χ L(G) ≤ n − 2 (ii) If G is planar and every triangle bounds a disk, then n − 3 ≤ χ L(G) ≤ n − 2