| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652480 | Electronic Notes in Discrete Mathematics | 2009 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
