Guillaume Fertin ; André Raspaud - Acyclic Coloring of Graphs of Maximum Degree Δ

dmtcs:3450 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3450
Acyclic Coloring of Graphs of Maximum Degree ΔConference paper

Authors: Guillaume Fertin ORCID1; André Raspaud 2

  • 1 Laboratoire d'Informatique de Nantes Atlantique
  • 2 Laboratoire Bordelais de Recherche en Informatique

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G, and is denoted by a(G). We show that any graph of maximum degree Δ has acyclic chromatic number at most Δ(Δ1)2 for any Δ5, and we give an O(nΔ2) algorithm to acyclically color any graph of maximum degree Δ with the above mentioned number of colors. This result is roughly two times better than the best general upper bound known so far, yielding a(G)Δ(Δ1)+2. By a deeper study of the case Δ=5, we also show that any graph of maximum degree 5 can be acyclically colored with at most 9 colors, and give a linear time algorithm to achieve this bound.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Acyclic chromatic number,acyclic coloring algorithm,maximum degree,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

5 Documents citing this article

Consultation statistics

This page has been seen 303 times.
This article's PDF has been downloaded 535 times.