Submit progress

on Coefficient of the acyclic chromatic index ($C_{55}$)

The statement

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$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.