## 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 - 2002 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Acyclic edge coloring
- Girth