![](/files/happy5.png)
edge coloring
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
![Syndicate content Syndicate content](/misc/feed.png)