(1, k)-Coloring of Graphs with Girth at Least Five on a Surface

A graph is (d(1),..., d(r))-colorable if its vertex set can be partitioned into r sets V-1,..., V-r so that the maximum degree of the graph induced by V-i is at most d(i) for each i is an element of {1,..., r}. For a given pair (g, d(1)), the question of determining the minimum d(2) = d(2)(g, d(1)) such that planar graphs with girth at least g are (d(1), d(2))-colorable has attracted much interest. The finiteness of d(2)(g, d(1)) was known for all cases except when (g, d(1)) = (5, 1). Montassier and Ochem explicitly asked if d(2)(5, 1) is finite. We answer this question in the affirmative with d(2)(5, 1) <= 10; namely, we prove that all planar graphs with girth at least five are (1, 10)-colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus gamma, there exists a K = K(gamma) where graphs with girth at least five that are embeddable on S are (1, K)-colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)-colorable. (C) 2016 Wiley Periodicals, Inc.