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)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)-cycle exists if and only if the chromatic number of the (2k + 1)th power of G(1/3) is less than or equal to 3, where G(1/3) is the 3-subdivision of G. We also consider Nesetril'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 Nesetril's problem are introduced and their relations are presented. (C) 2009 Elsevier B.V. All rights reserved.