On colorings of graph powers

In this paper, some results concerning the colorings of graph powers are presented. The notion of helical graphs is introduced. We show that such graphs are hom-universal with respect to high odd-girth graphs whose (2t+1)(2t+1)th power is bounded by a Kneser graph according to the homomorphism order. Also, we consider the problem of existence of homomorphism to odd cycles. We prove that such homomorphism to a (2k+1)(2k+1)-cycle exists if and only if the chromatic number of the (2k+1)(2k+1)th power of G13 is less than or equal to 3, where G13 is the 3-subdivision of GG. We also consider Nešetřil’s Pentagon problem. This problem is about the existence of high girth cubic graphs which are not homomorphic to the cycle of size five. Several problems which are closely related to Nešetřil’s problem are introduced and their relations are presented.