2025/11/03 by Marcin Anholcer, Anholcer, Marcin, Sylwia Cichacz +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2511.01532
Let G be a graph. An acyclic k-coloring of G is a map c:V(G)→ \1,…,k\ such that c(u)≠ c(v) for any uv∈ E(G) and the subgraph induced by the vertices of any two colors i,j∈ \1,…,k\ is a forest. If every vertex v of a color class Vi misses a color ℓv∈\1,…,k\ in its closed neighborhood, then every v∈ Vi can be recolored with ℓv and we obtain a (k-1)-coloring of G. If a new coloring c' is also acyclic, then such a recoloring is an acyclic recoloring step and c' is in relation \trianglelefta with c. The acyclic b-chromatic number Ab(G) of G is the maximum number of colors in an acyclic coloring where no acyclic recoloring step is possible. Equivalently, it is the maximum number of colors in a minimum element of the transitive closure of \trianglelefta. In this paper, we consider Ab(G) of cubic graphs.