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

摘要

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