The coefficient of the acyclic chromatic index

Description of constant

Let $G$ be a simple graph. The acyclic chromatic index $\chi_{a}’(G)$ of $G$ is defined to be the least number of colors needed to color the edges of $G$ so that no two edges coincident on the same vertex are homochromatic and there is no cycle whose edges are colored with only two colors.

Let $\Delta$ be the maximum degree of $G$. The coefficient of the acyclic chromatic index, here to be denoted by $C_{55}$, is defined to be the infimum of all $c$ such that for all $G$, $\chi_a’(G) \leq c \Delta +o(\Delta)$. Easily, $1 \leq C_{55}.$

It has been conjectured ([F1978], [ASZ2001]) that for all graphs, the acyclic chromatic index is at most $\Delta +2.$ A consequence of this conjecture would be that $C_{55} =1$.

Known upper bounds

Bound Reference Comments
16 [AMR1991], [MR1998]  
9.62 [NPS2012]  
4 [EP2013]  
3.74 [GKPT2017]  
4- [GKZ2018]  
3.569 [FLM2020]  
3.142 [KLS2026]  

Known lower bounds

Bound Reference Comments
1 Trivial conjectured to be sharp

References