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 Δ(Δ−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.
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.