Colouring clique-hypergraphs of circulant graphs (Q5925222)

A clique coloring of a graph \(G\) is a coloring 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 coloring of \(\mathcal{H}(G)\) is a clique coloring of \(G\). Determining the clique chromatic number, the least number of colors for which a graph \(G\) admits a clique coloring, is known to be NP-hard. In this paper, the authors show that the clique chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colors. For odd-seq circulant graphs, it is shown that their clique chromatic number is at most four. Some cases are determined, when it is equal to two. Some bounds for the chromatic number of these graphs are also obtained.