On coloring of fractional powers of graphs

Stephen Hartke, Hong Liu, Šárka Petříčková

Published 2012-12-17Version 1

For $m, n\in \N$, the fractional power $\Gmn$ of a graph $G$ is the $m$th power of the $n$-subdivision of $G$, where the $n$-subdivision is obtained by replacing each edge in $G$ with a path of length $n$. It was conjectured by Iradmusa that if $G$ is a connected graph with $\Delta(G)\ge 3$ and $1<m<n$, then $\chi(\Gmn)=\omega(\Gmn)$. Here we show that the conjecture does not hold in full generality by presenting a graph $H$ for which $\chi(H^{3/5})>\omega(H^{3/5})$. However, we prove that the conjecture is true if $m$ is even. We also study the case when $m$ is odd, obtaining a general upper bound $\chi(\Gmn)\leq \omega(\Gmn)+2$ for graphs with $\Delta(G)\geq 4$.