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 1; André Raspaud 2
0000-0002-8251-2012##NULL
Guillaume Fertin;André Raspaud
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.
Juan Wang;Lian Ying Miao;Jin Bo Li;Yun Long Liu, 2022, Acyclic Choosability of Graphs with Bounded Degree, Acta Mathematica Sinica English Series, 38, 3, pp. 560-570, 10.1007/s10114-022-0097-7.
Juan Wang;Lianying Miao;Wenyao Song;Yunlong Liu, 2020, Acyclic Coloring of Graphs with Maximum Degree 7, Graphs and Combinatorics, 37, 2, pp. 455-469, 10.1007/s00373-020-02254-w.
Guanghui Wang;Guiying Yan;Jiguo Yu;Xin Zhang, 2013, The r r -acyclic chromatic number of planar graphs, Journal of Combinatorial Optimization, 29, 4, pp. 713-722, 10.1007/s10878-013-9619-7.