1
$\begingroup$

Suppose we can color the vertices of powers of cycles $C_n^k$ using $c$ colors such that each of the color classes $c_i$ have $v_i$ number of vertices. Can we always color the circulant of degree $2k$ and order $n$ using the same $c$ colors such that each of the color classes $c_i$ have $v_i$ vertices.

I think yes. The main motivation for thinking so is that among the circulant graphs of given order and degree, I think the powers of cycles have the maximum clique size. So, the chromatic number of powers of cycles should always be greater than or equal to that of any circulant graph of same degree and order. Thus, if we could color the powers of cycles with $c$ colors the number of colors should suffice for any circulant graph of same order and degree. By a suitable permutation of vertices, I think the color classes also could be so arranged to have the same number of vertices as for the powers of cycles. Is this true? Thanks beforehand.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.