On Colorings of Graph Powers

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-403692

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.