Acyclic edge-coloring of planar graphs: colors suffice when is large

Abstract: An emph{acyclic edge-coloring} of a graph

G

is a proper edge-coloring of

G

such that the subgraph induced by any two color classes is acyclic. The emph{acyclic chromatic index},

c h i'_{a} (G)

, is the smallest number of colors allowing an acyclic edge-coloring of

G

. Clearly

c h i'_{a} (G) g e D e l t a (G)

for every graph

G

. Cohen, Havet, and M"{u}ller conjectured that there exists a constant

M

such that every planar graph with

D e l t a (G) g e M

has

c h i'_{a} (G) = D e l t a (G)

. We prove this conjecture.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Acyclic edge-coloring of planar graphs: \(\Delta\) colors suffice when \(\Delta\) is large