Premium
Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
Author(s) -
Cowen L. J.,
Cowen R. H.,
Woodall D. R.
Publication year - 1986
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190100207
Subject(s) - combinatorics , mathematics , planar graph , 1 planar graph , valency , outerplanar graph , discrete mathematics , vertex (graph theory) , colored , graph , chordal graph , pathwidth , line graph , linguistics , philosophy , materials science , composite material
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.