(1, <i>k</i>)‐Coloring of Graphs with Girth at Least Five on a Surface

Abstract

Abstract A graph is ‐colorable if its vertex set can be partitioned into r sets so that the maximum degree of the graph induced by is at most for each . For a given pair , the question of determining the minimum such that planar graphs with girth at least g are ‐colorable has attracted much interest. The finiteness of was known for all cases except when . Montassier and Ochem explicitly asked if d 2 (5, 1) is finite. We answer this question in the affirmative with ; 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 γ, there exists a 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.