Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency

摘要: We call a graph (m, k)-colorable if its vertices can be colored with m colors in such way that each vertex is adjacent to at most k of the same color as itself. For class planar graphs, and outerplanar we determine all pairs k) every k)-colorable. include an elementary proof (not assuming truth four-color theorem) (4, 1)-colorable. Finally, prove that, for compact surface S, there integer = k(S) S k)-colored; conjecture 4 replaced by 3 this statement.