Importance: High ✭✭✭
 Subject: Graph Theory
 Keywords: chromatic number, fractional power of graph, clique number
 Posted by: Iradmusa on: April 23rd, 2011
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.

## 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.