Vertex Coloring of graph fractional powers

Importance: High ✭✭✭

Author(s):

Subject:

Keywords:

chromatic number, fractional power of graph, clique number

Recomm. for undergrads: yes

Posted	by:	Iradmusa
	on:	April 23rd, 2011

Conjecture Let $G$ be a graph and $k$ be a positive integer. The $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 $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$ .
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.

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.

add new comment

Needs revision

On July 13th, 2011 Anonymous says:

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.

Open Problem Garden

Vertex Coloring of graph fractional powers

Bibliography

Needs revision

Comment viewing options

Navigate

Recent Activity