Hajós’ conjecture and cycle power graphs

Hajós’ conjecture says that every graph of chromatic number kk contains a subdivision of the complete graph with kk vertices. In this note, we give a characterization for cycle power graphs Cnk on Hajós’ conjecture, which generalized a recent result of Thomassen (2005) [C. Thomassen, Some remarks on Hajós’ conjecture, J. Combin. Theory Ser. B 93 (2005) 95105]. Precisely, we showed that for positive integers n,kn,k such that n>2k+1n>2k+1, and then n=q(k+1)+rn=q(k+1)+r, where 0≤r≤k0≤r≤k, the kkth power of the cycle CnCn, Cnk, satisfies Hajós’ conjecture if and only if 1+2+⋯+⌈r/q⌉≤k1+2+⋯+⌈r/q⌉≤k.