Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418507 | Discrete Applied Mathematics | 2016 | 9 Pages |
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].
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Younjin Kim, Sang June Lee, Sang-il Oum,