![](/files/happy5.png)
Samal, Robert
Star chromatic index of complete graphs ★★
Author(s): Dvorak; Mohar; Samal
Conjecture Is it possible to color edges of the complete graph
using
colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?
![$ K_n $](/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png)
![$ O(n) $](/files/tex/ee18510ab4140627d7a8df7949d309533b39ebca.png)
Equivalently: is the star chromatic index of linear in
?
Keywords: complete graph; edge coloring; star coloring
Star chromatic index of cubic graphs ★★
Author(s): Dvorak; Mohar; Samal
The star chromatic index of a graph
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
, we have
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \chi_s'(G) \le 6 $](/files/tex/939fe757ce3282a8fdccc122ba21e224cf9edd92.png)
Keywords: edge coloring; star coloring
Weak pentagon problem ★★
Author(s): Samal
Conjecture If
is a cubic graph not containing a triangle, then it is possible to color the edges of
by five colors, so that the complement of every color class is a bipartite graph.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon
Drawing disconnected graphs on surfaces ★★
Author(s): DeVos; Mohar; Samal
Conjecture Let
be the disjoint union of the graphs
and
and let
be a surface. Is it true that every optimal drawing of
on
has the property that
and
are disjoint?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G_1 $](/files/tex/1475475906abb943f311289729184c527071d32f.png)
![$ G_2 $](/files/tex/7c390ecd91deb4948e85912eba8f5594f03ea2f4.png)
![$ \Sigma $](/files/tex/70e73d02e8dfe5c2df3217d0bb04993df8dd0712.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \Sigma $](/files/tex/70e73d02e8dfe5c2df3217d0bb04993df8dd0712.png)
![$ G_1 $](/files/tex/1475475906abb943f311289729184c527071d32f.png)
![$ G_2 $](/files/tex/7c390ecd91deb4948e85912eba8f5594f03ea2f4.png)
Keywords: crossing number; surface
Cores of Cayley graphs ★★
Author(s): Samal
Conjecture Let
be an abelian group. Is the core of a Cayley graph (on some power of
) a Cayley graph (on some power of
)?
![$ M $](/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png)
![$ M $](/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png)
![$ M $](/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png)
Keywords: Cayley graph; core
![Syndicate content Syndicate content](/misc/feed.png)