Home » Subject » Graph Theory
Importance: Medium ✭✭
Author(s): Dvorak, Zdenek
Mohar, Bojan
Samal, Robert
Subject: Graph Theory
Keywords: complete graph
edge coloring
star coloring
Recomm. for undergrads: yes
Posted by: Robert Samal
on: November 16th, 2010
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 $?

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 line graph $ L(G) $.

Dvořák, Mohar, and Šámal [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.

Related problems

Star chromatic index of cubic graphs

Bibliography

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


* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options