(1, k)-coloring of graphs with girth at least 5 on a surface

Original · EN

A graph is (d₁,..., dᵣ)-colorable if its vertex set can be partitioned into r sets V₁,..., Vᵣ so that the maximum degree of the graph induced by Vᵢ is at most dᵢ for each i∈ {1,..., r}. For a given pair (g, d₁), the question of determining the minimum d₂=d₂(g; d₁) such that planar graphs with girth at least g are (d₁, d₂)-colorable has attracted much interest. The finiteness of d₂(g; d₁) was known for all cases except when (g, d₁)=(5, 1). Montassier and Ochem explicitly asked if d₂(5; 1) is finite. We answer this question in the affirmative with d₂(5; 1)≤ 10; namely, we prove that all planar graphs with girth at least 5 are (1, 10)-colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a K=K(γ) where graphs with girth at least 5 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 5 are (0, k)-colorable.