Title of article
Clique-Coloring Circular-Arc Graphs
Author/Authors
Cerioli، نويسنده , , Mلrcia R. and Korenchendler، نويسنده , , André L.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
6
From page
287
To page
292
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.
Keywords
graph theory , Clique-coloring , circular-arc graph , interval graph
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2009
Journal title
Electronic Notes in Discrete Mathematics
Record number
1455317
Link To Document