On Coloring of Fractional Powers of Star, Wheel, Friendship, and Fan Graphs

Abstract

Let $G$ be a simple, connected, and undirected graph. For $ m, n \in \mathbb{N} $, the fractional power $ G^{\frac{m}{n}} = \left( G^{\frac{1}{n}} \right)^m $ of $ G $ is constructed by taking the $ n $-subdivision of $ G $ (replacing each edge by a path of length $ n $), and then raising the resulting graph to the $ m $-th power (connecting any two distinct vertices with distance at most m).Let $omega(G)$ be a clique number of $G$ and $\chi(G)$ be the chromatic number of $G$. Iradmusa formulated a closed form for the clique number of $ G^{\frac{m}{n}} $ ($ \omega(G^{\frac{m}{n}}) $) and conjectured that $\chi(G^{\frac{m}{n}}) = \omega(G^{\frac{m}{n}}) $ for every $ m, n \in \mathbb{N} $ where $ \frac{m}{n} < 1 $ and $ \Delta(G) \geq 3 $. The conjecture is true for certain special cases, such as paths, cycles and complete graphs. However, Hartke et. al. found a counterexample of the conjecture, that is the graph $ G = C_3 \square K_2 $ when $ m = 3 $ and $ n = 5 $. In this paper, we aim to prove that the conjecture is true for some classes of graphs that is not yet addressed. We prove that $\chi(G^{\frac{m}{n}}) = \omega(G^{\frac{m}{n}}) $ for star, wheel, friendship, and fan graphs $G$.