K₅-Minor-Free Graphs Are Acyclically 5-Colorable

A 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 cyclecan exist in G Graph H is called a minor of graph G if it can be obtainedby means of a sequence of vertex and edge deletions and edge contractionsIn 2006 Borodin showed that all planar graphs are acyclically 5-colorableIn this paper the result is generalized to allK一minor—free graphs...