k-forested choosability of planar graphs and sparse graphs

AbstractA proper vertex coloring of a simple graph G is k-forested if the subgraph induced by the vertices of any two color classes is a k-forest, i.e. a forest with maximum degree at most k. The 2-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 2-forested coloring to general k-forested colorings for every k≥3 by combinatorial means. Precisely, we prove that for a fixed integer k≥3 and a planar graph G with maximum degree Δ(G)≥Δ and girth g(G)≥g, if (Δ,g)∈{(k+1,10),(2k+1,8),(4k+1,7)}, then the k-forested chromatic number of G is actually ⌈Δ(G)k⌉+1. Moreover, we also prove that the k-forested chromatic number of a planar graph G with maximum degree Δ(G)≥k+1 and girth g(G)≥8 is ⌈Δ(G)k⌉+1 provided k≥7. In addition, we show that the k-forested chromatic number of an outerplanar graph G is at most ⌈Δ(G)k⌉+2 for every k≥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