Article ID Journal Published Year Pages File Type
418507 Discrete Applied Mathematics 2016 9 Pages PDF
Abstract

We prove that every simple connected graph with no K5K5 minor admits a proper 4-coloring such that the neighborhood of each vertex vv having more than one neighbor is not monochromatic, unless the graph is isomorphic to the cycle of length 5. This generalizes the result on planar graphs by S.-J. Kim, W.-J. Park and the second author [Discrete Appl. Math. 161 (2013) 2207–2212].

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,