edge coloring


Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

\begin{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$? \end{conjecture}

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.

\begin{question} Is it true that for every (sub)cubic graph $G$, we have $\chi_s'(G) \le 6$? \end{question}

Keywords: edge coloring; star coloring

Syndicate content