Home » Author index

Iradmusa, Moharram


Graph Theory

Vertex Coloring of graph fractional powers ★★★

Author(s): Iradmusa

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.

Keywords: chromatic number, fractional power of graph, clique number

Posted by Iradmusa
updated July 13th, 2011
1 comment
Graph Theory » Coloring » Vertex coloring

Partial List Coloring ★★★

Author(s): Iradmusa

Let $ G $ be a simple graph, and for every list assignment $ \mathcal{L} $ let $ \lambda_{\mathcal{L}} $ be the maximum number of vertices of $ G $ which are colorable with respect to $ \mathcal{L} $. Define $ \lambda_t = \min{ \lambda_{\mathcal{L}} } $, where the minimum is taken over all list assignments $ \mathcal{L} $ with $ |\mathcal{L}| = t $ for all $ v \in V(G) $.

Conjecture   [2] Let $ G $ be a graph with list chromatic number $ \chi_\ell $ and $ 1\leq r\leq s\leq \chi_\ell $. Then \[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]

Keywords: list assignment; list coloring

Posted by Iradmusa
updated May 12th, 2008
add new comment
Syndicate content