kk-forested choosability of planar graphs and sparse graphs

A proper vertex coloring of a simple graph GG is kk-forested if the subgraph induced by the vertices of any two color classes is a kk-forest, i.e. a forest with maximum degree at most kk. The 22-forested coloring is also known as linear coloring, which has been extensively studied in the literature. In this paper, we aim to extend the study of 22-forested coloring to general kk-forested colorings for every k≥3k≥3 by combinatorial means. Precisely, we prove that for a fixed integer k≥3k≥3 and a planar graph GG with maximum degree Δ(G)≥ΔΔ(G)≥Δ and girth g(G)≥gg(G)≥g, if (Δ,g)∈{(k+1,10),(2k+1,8),(4k+1,7)}(Δ,g)∈{(k+1,10),(2k+1,8),(4k+1,7)}, then the kk-forested chromatic number of GG is actually ⌈Δ(G)k⌉+1. Moreover, we also prove that the kk-forested chromatic number of a planar graph GG with maximum degree Δ(G)≥k+1Δ(G)≥k+1 and girth g(G)≥8g(G)≥8 is ⌈Δ(G)k⌉+1 provided k≥7k≥7. In addition, we show that the kk-forested chromatic number of an outerplanar graph GG is at most ⌈Δ(G)k⌉+2 for every k≥2k≥2. In fact, all these results are proved for not only planar graphs but also for sparse graphs, i.e. graphs having a low maximum average degree mad(G), and we actually prove a choosability version of these results.