Dynamic coloring of graphs having no $K_5$ minor

Abstract

We prove that every simple connected graph with no $K_5$ minor admits a proper 4-coloring such that the neighborhood of each vertex $v$ having more than one neighbor is not monochromatic, unless the graph is isomorphic to the cycle of length 5. This generalizes the result by S.-J. Kim, S. J. Lee, and W.-J. Park on planar graphs.

Rewriting with a major change (14 pages, 1 figure)

References in corpus (2)

• On r-dynamic Coloring of Grids
• A generalization of the Erdős-Ko-Rado Theorem

Cited by in corpus (2)

• Dynamic list coloring of 1-planar graphs
• A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs