Hajós’ conjecture and cycle power graphs

AbstractHajós’ conjecture says that every graph of chromatic number k contains a subdivision of the complete graph with k 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,k such that n>2k+1, and then n=q(k+1)+r, where 0≤r≤k, the kth power of the cycle Cn, Cnk, satisfies Hajós’ conjecture if and only if 1+2+⋯+⌈r/q⌉≤k