Equitable clique-coloring in claw-free graphs with maximum degree at most 4 (Q2657098)

A clique of a graph \(G\) is a set of pairwise adjacent vertices of \(G\). A clique on \(m\) vertices is called an \(m\)-clique of \(G\). A clique-coloring, also known as weak coloring, is an assignment of colors to the vertices of \(G\) in such a way that no inclusion-wise maximal clique of size at least two is monochromatic. An equitable vertex-coloring of \(G\) is a proper vertex-coloring such that any two color classes differ in size by at most one. An equitable clique-coloring of \(G\) is a clique-coloring such that any two color classes differ in size by at most one. If \(G\) has an equitable clique-coloring with \(k\) colors, we say that \(G\) is equitably \(k\)-clique colorable. The purpose of the paper is to show that every connected claw-free graph with maximum degree at most four, other than an odd cycle greater than three, is also equitably 2-clique-colorable, where the claw is the complete bipartite graph \(K(1;3)\). The paper also gives an algorithm for an equitable 2-clique-coloring in linear time for this class of graphs.