
chromatic number, fractional power of graph, clique number
Vertex Coloring of graph fractional powers โ โ โ
Author(s): Iradmusa
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.
Keywords: chromatic number, fractional power of graph, clique number
