### Abstract

A proper coloring of the edges of a graph G is called acyclic if there is no 2-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) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G)≤Δ + 2 for almost all Δ-regular graphs.

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

Pages (from-to) | 157-167 |

Number of pages | 11 |

Journal | Journal of Graph Theory |

Volume | 37 |

Issue number | 3 |

DOIs | |

State | Published - Jul 2001 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Geometry and Topology

### Keywords

- Acyclic chromatic number
- Acyclic edge coloring
- Graph

## Fingerprint Dive into the research topics of 'Acyclic edge colorings of graphs'. Together they form a unique fingerprint.

## Cite this

Alon, N., Sudakov, B., & Zaks, A. (2001). Acyclic edge colorings of graphs.

*Journal of Graph Theory*,*37*(3), 157-167. https://doi.org/10.1002/jgt.1010