On Coloring Properties of Graph Powers

الأصل · EN

This paper studies some coloring properties of graph powers. We show that χc(G²ʳ⁺¹/²ˢ⁺¹)=(2s+1)χc(G)/(s-r)χc(G)+2r+1 provided that χc(G²ʳ⁺¹/²ˢ⁺¹)< 4. As a consequence, one can see that if 2r+1 2s+1 ≤ χc(G) 3(χc(G)-2), then χc(G²ʳ⁺¹/²ˢ⁺¹)=(2s+1)χc(G)/(s-r)χc(G)+2r+1. In particular, χc(K₃ₙ₊₁13)=9n+3 3n+2 and K₃ₙ₊₁13 has no subgraph with circular chromatic number equal to 6n+1 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¹/²ˢ⁺¹)≤ (2s+1)χf(G)/sχf(G)+1. Finally, we investigate the nth multichromatic number of subdivision graphs.