Improved bounds for acyclic coloring parameters

arXiv2202.13846MaRDI QIDQ6507746FDOQ6507746

Authors: L. M. Kirousis, John Livieratos 

Abstract: The acyclic chromatic number of a graph is the least number of colors needed to properly color its vertices so that none of its cycles has only two colors. The acyclic chromatic index is the analogous graph parameter for edge colorings. We first show that the acyclic chromatic index is at most $2Delta-1$, where $Delta$ is the maximum degree of the graph. We then show that for all $epsilon>0$ and for $Delta$ large enough (depending on $epsilon$), the acyclic chromatic number of the graph is at most $lceil(2^{-1/3}+epsilon){Delta}^{4/3}ceil+Delta+1$. Both results improve long chains of previous successive advances. Both are algorithmic, in the sense that the colorings are generated by randomized algorithms. However, in contrast with extant approaches, where the randomized algorithms assume the availability of enough colors to guarantee properness deterministically, and use additional colors for randomization in dealing with the bichromatic cycles, our algorithms may initially generate colorings that are not necessarily proper; they only aim at avoiding cycles where all pairs of edges, or vertices, that are one edge, or vertex, apart in a traversal of the cycle are homochromatic (of the same color). When this goal is reached, they check for properness and if necessary they repeat until properness is attained.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

This page was built for publication: Improved bounds for acyclic coloring parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507746)