Planar graphs with girth at least 5 are (3,4)-colorable

A graph is (d(1), ..., d(k))-colorable if its vertex set can be partitioned into k nonempty subsets so that the subgraph induced by the ith part has maximum degree at most d(i) for each i is an element of {1, ..., k}. It is known that for each pair (d(1), d(2)), there exists a planar graph with girth 4 that is not (d(1), d(2))-colorable. This sparked the interest in finding the pairs (d(1), d(2)) such that planar graphs with girth at least 5 are (d(1), d(2))-colorable. Given d(1) <= d(2) , it is known that planar graphs with girth at least 5 are (d(1), d(2))-colorable if either d(1) >= 2 and d(1) + d(2) >= 8 or d(1) = 1 and d(2) >= 10. We improve an aforementioned result by providing the first pair (d(1), d(2)) in the literature satisfying d(1) + d(2) <= 7 where planar graphs with girth at least 5 are (d(1), d(2) )-colorable. Namely, we prove that planar graphs with girth at least 5 are (3, 4)-colorable. (C) 2019 Elsevier B.V. All rights reserved.