Vertex Coloring of graph fractional powers

Importance: High ✭✭✭
Author(s): Iradmusa, Moharram
Subject: Graph Theory
Recomm. for undergrads: yes
Posted by: Iradmusa
on: April 23rd, 2011

\begin{conjecture} Let $G$ be a graph and $k$ be a positive integer. The \emph{$k-$power of $G$}, denoted by $G^k$, is defined on the vertex set $V(G)$, by connecting any two distinct vertices $x$ and $y$ with distance at most $k$. In other words, $E(G^k)=\{xy:1\leq d_G(x,y)\leq k\}$. Also \emph{$k-$subdivision of $G$}, denoted by $G^\frac{1}{k}$, is constructed by replacing each edge $ij$ of $G$ with a path of length $k$. Note that for $k=1$, we have $G^\frac{1}{1}=G^1=G$.\\ Now we can define the fractional power of a graph as follows:\\ Let $G$ be a graph and $m,n\in \mathbb{N}$. The graph $G^{\frac{m}{n}}$ is defined by the $m-$power of the $n-$subdivision of $G$. In other words $G^{\frac{m}{n}}\isdef (G^{\frac{1}{n}})^m$.\\ \emph{Conjecture.} Let $G$ be a connected graph with $\Delta(G)\geq3$ and $m$ be a positive integer greater than 1. Then for any positive integer $n>m$, we have $\chi(G^{\frac{m}{n}})=\omega(G^\frac{m}{n})$.\\ In [1], it was shown that this conjecture is true in some special cases. \end{conjecture}


[1] Iradmusa, Moharram N., On colorings of graph fractional powers. Discrete Math. 310 (2010), no. 10-11, 1551–1556.

* indicates original appearance(s) of problem.

Needs revision

Note that if K_t is the complete graph on t vertices with t even, then the 2-power of the 2-subdivision of K_t is isomorphic to the total graph of K_t. That is the graph T(K_t) whose vertex set is V(K_t) union E(K_t) and two vertices are adjacent in T(K_t) if their either adjacent or incident in K_t.

clique number of T(K_t) is t + 1 and the chromatic number of T(K_t) is >= t+2.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.