
Vertex Coloring of graph fractional powers
Conjecture Let
be a graph and
be a positive integer. The
power of
, denoted by
, is defined on the vertex set
, by connecting any two distinct vertices
and
with distance at most
. In other words,
. Also
subdivision of
, denoted by
, is constructed by replacing each edge
of
with a path of length
. Note that for
, we have
.
Now we can define the fractional power of a graph as follows:
Let
be a graph and
. The graph
is defined by the
power of the
subdivision of
. In other words
.
Conjecture. Let
be a connected graph with
and
be a positive integer greater than 1. Then for any positive integer
, we have
.
In [1], it was shown that this conjecture is true in some special cases.


















Now we can define the fractional power of a graph as follows:
Let







Conjecture. Let





In [1], it was shown that this conjecture is true in some special cases.
Bibliography
[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.