Open Problem Garden

Graph Theory » Coloring » Vertex coloring

Ohba's Conjecture ★★

Author(s): Ohba

Conjecture If $|V(G)|\leq 2\chi(G)+1$ , then $\chi_\ell(G)=\chi(G)$ .

Keywords: choosability; chromatic number; complete multipartite graph; list coloring

Posted by Jon Noel
updated May 18th, 2011

add new comment | 2 attachments

Number Theory

Primitive pythagorean n-tuple tree ★★

Author(s):

Conjecture Find linear transformation construction of primitive pythagorean n-tuple tree!

Keywords:

Posted by tsihonglau
updated June 16th, 2021

1 comment

chromatic number, fractional power of graph, clique number

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