Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs

For nonnegative integers k, d₁, …, dₖ, a graph is (d₁, …, dₖ)-colorable if its vertex set can be partitioned into k parts so that the ith part induces a graph with maximum degree at most dᵢ for all i∈\1, …, k\. A class C of graphs is balanced k-partitionable and unbalanced k-partitionable if there exists a nonnegative integer D such that all graphs in C are (D, …, D)-colorable and (0, …, 0, D)-colorable, respectively, where the tuple has length k. A set X of cycles is a cycle obstruction set of a class C of planar graphs if every planar graph containing none of the cycles in X as a subgraph belongs to C. This paper characterizes all cycle obstruction sets of planar graphs to be balanced k-partitionable and unbalanced k-partitionable for all k; namely, we identify all inclusionwise minimal cycle obstruction sets for all k.