Samal, Robert

Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

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

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

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

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

Cores of Cayley graphs ★★★★★

Author(s): Samal

Conjecture   Let $ M $ be an abelian group. Is the core of a Cayley graph (on some power of $ M $) a Cayley graph (on some power of $ M $)?

Keywords: Cayley graph; core

Syndicate content