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 ∈ ℕ, the fractional power G^m/n = (G^1/n)^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 ω(G) be a clique number of G and χ(G) be the chromatic number of G. Iradmusa formulated a closed form for the clique number of G^m/n(ω(G^m/n)) and conjectured that χ(G^m/n) = ω(G^m/n) for every m, n ∈ ℕ where m/n < 1 and ∆(G) ≥ 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₃ ↆ K₂ 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 χ(G^m/n) = ω(G^m/n) for star, wheel, friendship, and fan graphs G.