For nonnegative integers $k, d_1, ldots, d_k$, a graph is $(d_1, ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $iin{1, ldots, k}$. A class $mathcal C$ of graphs is {it balanced $k$-partitionable} and {it unbalanced $k$-partitionable} if there exists a nonnegative integer $D$ such that all graphs in $mathcal C$ are $(D, ldots, D)$-colorable and $(0, ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a {it cycle obstruction set} of a class $mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $mathcal 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 inclusion-wise minimal cycle obstruction sets for all $k$.
تحميل البحث