**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?

Equivalently: is the star chromatic index of linear in ?

The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of so that no path or cycle of length four is bi-colored. An equivalent definition is that is the star chromatic number of the line graph .

Dvořák, Mohar, and Šámal [DMS] show that . On the other hand, the best known upper bound (also in \cite{DMS]) is superlinear:

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

## Bibliography

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

* indicates original appearance(s) of problem.