2011/04/22 by Hossein Hajiabolhassan, Hajiabolhassan, Hossein, Ali Taherkhani +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1104.4411
arxiv created 2011/04/22 · arxiv updated 2011/04/25
This paper studies some coloring properties of graph powers. We show that χc(G^(2r+1)/(2s+1))=((2s+1)χc(G))/((s-r)χc(G)+2r+1) provided that χc(G^(2r+1)/(2s+1))< 4. As a consequence, one can see that if 2r+1 \over 2s+1 ≤ χc(G) \over 3(χc(G)-2), then χc(G^(2r+1)/(2s+1))=((2s+1)χc(G))/((s-r)χc(G)+2r+1). In particular, χc(K3n+1^1\over3)=9n+3\over 3n+2 and K3n+1^1\over3 has no subgraph with circular chromatic number equal to 6n+1\over 2n+1. This provides a negative answer to a question asked in [Xuding Zhu, Circular chromatic number: a survey, Discrete Math., 229(1-3):371--410, 2001]. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that χf(G^(1)/(2s+1))≤ ((2s+1)χf(G))/(sχf(G)+1). Finally, we investigate the nth multichromatic number of subdivision graphs.