Samal, Robert

Star chromatic index of complete graphs ★★

Conjecture Is it possible to color edges of the complete graph $K_n$ using $O(n)$ colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?

Equivalently: is the star chromatic index of $K_n$ linear in $n$ ?

Keywords: complete graph; edge coloring; star coloring

Posted by Robert Samal
updated November 16th, 2010

add new comment

Graph Theory

Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

Question Is it true that for every (sub)cubic graph $G$ , we have $\chi_s'(G) \le 6$ ?

Keywords: edge coloring; star coloring

Posted by Robert Samal
updated November 16th, 2010

add new comment

Graph Theory » Coloring » Homomorphisms

Weak pentagon problem ★★

Author(s): Samal

Conjecture If $G$ is a cubic graph not containing a triangle, then it is possible to color the edges of $G$ by five colors, so that the complement of every color class is a bipartite graph.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

Posted by Robert Samal
updated July 13th, 2007

add new comment

Graph Theory » Topological G.T. » Crossing numbers

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture Let $G$ be the disjoint union of the graphs $G_1$ and $G_2$ and let $\Sigma$ be a surface. Is it true that every optimal drawing of $G$ on $\Sigma$ has the property that $G_1$ and $G_2$ are disjoint?

Keywords: crossing number; surface

Posted by mdevos
updated September 30th, 2007

1 comment

Graph Theory » Coloring » Homomorphisms