Abstract:

A clique is defined as a complete subgraph  maximal under inclusion and having at least two vertices.   A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no clique of G is monochromatic.  If G has a  k-clique-coloring, we say that G  is k-clique-colorable. The clique-coloring number  \chi_{C}(G)  is the smallest  integer  k admitting a  k-clique-coloring of G.  In this paper,  we first point out a relation between the clique-coloring number of line graphs of complete graphs  and the generalized Ramsey number. Secondly, we give a polynomial time algorithm for the optimal clique-coloring problem in line graphs of maximum  degree at most 7.

Key words: clique-coloring, polynomial-time algorithm, line graph, complete graph