Vertex colorings of fractional powers (2010)

Originators: Moharram N. Iradmusa    (presented by Sarka Petrickova - REGS 2011)

Definitions: Let $G$ be a simple finite graph, and let $m$ and $n$ be positive integers. The $n$-subdivision of $G$, denoted by $G^{{1}/{n}}$, is the graph that arises from $G$ by replacing each edge with a path of length $n$. The $m$-power of $G$, denoted by $G^m$, is the graph constructed from $G$ by joining every two distinct vertices with distance at most $m$. The fractional power $G^{{m}/{n}}$ is then defined to be the $m$-power of the $n$-subdivision of $G$; that is, $G^{{m}/{n}}=(G^{{1}/{n}})^m$.

Question: What can be said about the chromatic number of $G^{{m}/{n}}$ in terms of other parameters or properties of $G$?

Background: A total coloring of $G$ is a coloring of its vertices and edges such that no adjacent vertices, no adjacent edges, and no incident edge and vertex have the same color. The total chromatic number $\chi''(G)$ of $G$ is the least number of colors in such a coloring. The famous Total Coloring Conjecture by Vizing [V] and Behzad [B] states that $\chi''(G)\leq \Delta(G) + 2$ for any simple graph $G$. Since $\chi''(G)=\chi(G^{{2}/{2}})$, and $\omega(G^{{2}/{2}})=\Delta(G) + 1$ for every graph $G$ with $\Delta(G)\geq 2$, we can rewrite the Total Coloring Conjecture as follows:

Total Coloring Conjecture: [B,V] If $G$ is a simple graph maximum degree at least $2$, then $\chi(G^{{2}/{2}})\leq \omega(G^{{2}/{2}}) + 1.$

When $m\lt n$, the cliques corresponding to the original vertices of $G$ are somewhat separated, and an analogous conjecture has been made:

Conjecture 1: (Iradmusa [I]) If $G$ is a connected graph with $\Delta(G)\geq 3$ and $1\lt m\lt n$, then $\chi(G^{{m}/{n}})=\omega(G^{{m}/{n}})$.

Comments: Students in REGS (Liu and Petricova) have disproved the conjecture by finding an infinite family of graphs $G$ such that $\chi(G^{{m}/{n}})\gt\omega(G^{{m}/{n}})$ when $m$ and $n$ are appropriately chosen. Thus instead we should ask when the equality holds. Iradmusa [I] proved the following results

  1. Conjecture 1 holds for $m=2$.
  2. If $m\lt n$ and $\chi(G^{{m}/{n}})=\omega(G^{{m}/{n}})$, then $\chi(G^{{m}/(n+m+1)})=\omega(G^{{m}/(n+m+1)})$.
  3. If $G$ is a connected graph with $\Delta(G)\geq 3$, then $\chi(G^{{m}/(m+1)})=\omega(G^{{m}/(m+1)})$.
  4. Suppose that $n\ge 2m+2$. If $m$ is even and $\Delta(G)\geq 4$, or if $m$ is odd and $\Delta(G)\geq 5$, then $\chi(G^{{m}/{n}})=\omega(G^{{m}/{n}})$.
The students in REGS also generalized some ideas of [I] to prove that $\chi(G^{{m}/{n}})=\omega(G^{{m}/{n}})$ when $G$ is a class $1$ graph, $\Delta(G)\geq 4$, and $m$ is even.

References:
[B] M. Behzad, Graphs and their chromatic numbers, Ph.D. Thesis, Michigan State University, 1965.
[I] M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), 1551-1556.
[V] V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117-134.