Clique-chromatic Numbers of Line Graphs

Abstract

The clique-chromatic number of a graph is the least number of colors on the vertices of the graph without a monocolored maximal clique of size at least two.In \(2004\), Bacsé et al. proved that the family of line graphs has no bounded clique-chromatic number. In particular, the Ramsey numbers provide a sequence of the line graphs of complete graphs with no bounded clique-chromatie number. We
complete this result by giving the exact values of the clique-chromatic numbers of the line graphs of complete graphs in terms of Ramsey numbers. Furthermore, the clique-chromatic numbers of the line graphs of triangle-free graphs are characterized.