Iradmusa, Moharram


Vertex Coloring of graph fractional powers ★★★

Author(s): Iradmusa

\begin{conjecture} Let $G$ be a graph and $k$ be a positive integer. The \emph{$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 \emph{$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$.\\ \emph{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. \end{conjecture}

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

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)$.

\begin{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}.\] \end{conjecture}

Keywords: list assignment; list coloring

Syndicate content