# Acyclic edge-colouring

**Conjecture**Every simple graph with maximum degree has a proper -edge-colouring so that every cycle contains edges of at least three distinct colours.

An edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an *acyclic* edge-colouring. It is known (see [AMR]) that every graph of maximum degree has an acyclic edge-colouring of size . The best upper bound so far is and is due to Esperet and Parreau [EP]. It is also known (see [ASZ]) that this conjecture is true for graphs with girth at least (for some fixed constant ).

## Bibliography

[AMR] N. Alon, C. McDiarmid and B. Reed, Acyclic colouring of graphs, Random Structures and Algorithms 2 (1991), 277-288. MathSciNet

[ASZ] N. Alon, B. Sudakov and A. Zaks, Acyclic edge-colorings of graphs, J. Graph Theory 37 (2001), 157-167. MathSciNet

[EP] L. Esperet and A. Parreau, Acyclic edge-coloring using entropy compression, arXiv:1206.1535 [math.CO].

* indicates original appearance(s) of problem.