Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests

Abstract In 1976, Steinberg conjectured that planar graphs without 4-cycles and 5-cycles are 3-colorable. This conjecture attracted numerous researchers for about 40 years, until it was recently disproved by Cohen-Addad et al. (2017). However, coloring planar graphs with restrictions on cycle lengths is still an active area of research, and the interest in this particular graph class remains. Let G be a planar graph without 4-cycles and 5-cycles. For integers d 1 and d 2 satisfying d 1 + d 2 ≥ 8 and d 2 ≥ d 1 ≥ 2 , it is known that V ( G ) can be partitioned into two sets V 1 and V 2 , where each V i induces a graph with maximum degree at most d i . Since Steinberg’s Conjecture is false, a partition of V ( G ) into two sets, where one induces an empty graph and the other induces a forest is not guaranteed. Our main theorem is at the intersection of the two aforementioned research directions. We prove that V ( G ) can be partitioned into two sets V 1 and V 2 , where V 1 induces a forest with maximum degree at most 3 and V 2 induces a forest with maximum degree at most 4; this is both a relaxation of Steinberg’s conjecture and a strengthening of results by Sittitrai and Nakprasit (2019) in a much stronger form.