Processing math: 50%

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 \frac{\Delta (\Delta -1) }{ 2} for any \Delta \geq 5, and we give an O(n \Delta^2) algorithm to acyclically color any graph of maximum degree \Delta 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) \leq \Delta (\Delta -1) +2. By a deeper study of the case \Delta =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.