Star chromatic index of complete graphs

Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: yes
Posted by: Robert Samal
on: November 16th, 2010

\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}

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

Dvořák, Mohar, and Šámal \cite{DMS] show that $\chi_s'(G) \ge (2+o(1))n$. On the other hand, the best known upper bound (also in \cite{DMS}) is superlinear: $$ \chi_s'(K_n) \le n \cdot \frac{ 2^{ 2\sqrt2(1+o(1)) \sqrt{\log n} } }{(\log n)^{1/4}} \,. $$

It may be possible to decrease the upper bound by elementary methods.


*[DMS] Dvořák, Zdeněk; Mohar, Bojan; Šámal, Robert: Star chromatic index, \arXiv{1011.3376}.

* indicates original appearance(s) of problem.