Clique-Coloring Circular-Arc Graphs

A clique-coloring of a graph is a coloring of its vertices such that no maximal clique of size at least two is monochromatic. A circular-arc graph is the intersection graph of a family of arcs in a circle. We show that every circular-arc graph is 3-clique-colorable. Moreover, we characterize which circular-arc graphs are 2-clique-colorable. Our proof is constructive and gives a polynomial-time algorithm to find an optimal clique-coloring of a given circular-arc graph.