### Abstract

A proper coloring of the edges of a graph G is called acyclic if there is no two-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ Δ A + 2 for almost all Delta;-regular graphs, including all A-regular graphs whose girth is at least cΔ log A. We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs G with sufficiently large girth in terms of Δ(G), we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G) + 2 colors.

Original language | English (US) |
---|---|

Pages (from-to) | 611-614 |

Number of pages | 4 |

Journal | Algorithmica (New York) |

Volume | 32 |

Issue number | 4 |

DOIs | |

State | Published - Jan 1 2002 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics

### Keywords

- Acyclic edge coloring
- Girth

## Fingerprint Dive into the research topics of 'Algorithmic aspects of acyclic edge colorings'. Together they form a unique fingerprint.

## Cite this

*Algorithmica (New York)*,

*32*(4), 611-614. https://doi.org/10.1007/s00453-001-0093-8