On Colorings of Graph Powers

Details On Colorings of Graph Powers On Colorings of Graph Powers

2007-08-06

arxiv.org/abs/0708.0704v5

Mathematics

Combinatorics

Scientific paper

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)$st power is bounded by a Kneser graph. 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)$st power of $S_2(G)$ is less than or equal to 3, where $S_2(G)$ is the 2-subdivision of $G$. We also consider Ne\v{s}et\v{r}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\v{s}et\v{r}il's problem are introduced and their relations are presented.

Affiliated with

Also associated with

No associations

Rating

On Colorings of Graph Powers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Colorings of Graph Powers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Colorings of Graph Powers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-403692