@techreport{TR-IC-10-23,
number = {IC-10-23},
author = {C. N. Campos and S. Dantas and C. P. de Mello},
title = {Clique-colouring of some circulant graphs},
month = {July},
year = {2010},
institution = {Institute of Computing, University of Campinas},
note = {In English, 15 pages.
\par\selectlanguage{english}\textbf{Abstract}
A clique-colouring of a graph $G$ is a colouring of the
vertices of $G$ so that no maximal clique of size at least two
is monochromatic. The clique-hypergraph, $\mathcal{H}(G)$, of a
graph $G$ has $V(G)$ as its set of vertices and the maximal
cliques of $G$ as its hyperedges. A vertex-colouring of
$\mathcal{H}(G)$ is a clique-colouring of $G$. Determining the
clique-chromatic number, the least number of colours for which
a graph $G$ admits a clique-colouring, is known to be
\emph{NP}-hard. By determining some structural properties of
powers of cycles, we establish that the clique-chromatic number
of these graphs is equal to two, except for odd cycles of size
at least five, that need three colours. For odd-seq circulant
graphs, we show that their clique-chromatic number is at most
four, and determine the cases when it is equal to two. Similar
bounds for the chromatic number of these graphs are also
obtained.
}
}