Needs revision (re: Vertex Coloring of graph fractional powers)

Anonymous — Wed, 13 Jul 2011 02:47:13 +0200

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.

Vertex Coloring of graph fractional powers

Iradmusa — Sat, 23 Apr 2011 17:11:02 +0200

Author(s): Iradmusa

Subject: Graph Theory

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.

Open Problem Garden - Vertex Coloring of graph fractional powers - Comments

Needs revision (re: Vertex Coloring of graph fractional powers)

Vertex Coloring of graph fractional powers