On Coloring of Fractional Powers of Star, Wheel, Friendship, and Fan Graphs - Hafizh, Farisan; Maulana, Muhammad Rayhanafraa Gibran; Vienny, Citius; Joyosumarto, Bisma Rohpanca; Sugeng, Kiki A. (Indonesian Combinatorial Society (InaCombS), 2025)
Let G be a simple, connected, and undirected graph. For m, n ∈ ℕ, the fractional power Gm/n = (G1/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 Gm/n(ω(Gm/n)) and conjectured that χ(Gm/n) = ω(Gm/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 = C3 ↆ K2 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 χ(Gm/n) = ω(Gm/n) for star, wheel, friendship, and fan graphs G.