Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way.

It is well known that $\alpha'(G)$ is linear in $\Delta(G)$ and the best current bound seems to be $$\alpha'(G) \leq 4\Delta(G)-4,$$ obtained by what they call the entropy compression method.

Now consider you want to properly edge color your graph such that no 5-path is bi-colored and denote this number by $\beta'(G).$ Repeating the same argument with entropy compression one obtains an upper bound of order $O(\Delta(G)^{1.5})$ for $\beta'(G).$

If we consider the complete graph then it follows from here that $$\beta'(K_n) \leq n^{1+\epsilon}$$ for any fixed $\epsilon > 0.$

So while a linear number of color suffices to properly edge color a graph avoiding bi-colored cycles of any lenght it seems that the same problem is already much more complicated if we want to avoid just bi-colored 5-paths.

Given this I am wondering

Can you properly edge color $K_n$ such that no $5$-path is bi-colored and so that only a number of colors that is linear in $n$ is used?

  • 3
    $\begingroup$ Note that this question is precisely "Question 1" in the paper of Dvorak, Mohar and Samal you mentioned above. I believe that it is quite hard. The same question was also raised by Erdos and Gyarfas in 1997 (see page 22 in the following slides of Gyarfas at the Erdos Centennial conference renyi.hu/conferences/erdos100/slides/gyarfas.pdf), although Dvorak, Mohar and Samal did not seem to be aware of it. $\endgroup$ – Louis Esperet Jun 2 '15 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.