Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
Academic Article
Overview
Identity
Additional Document Info
View All
Overview
abstract
2018 Society for Industrial and Applied Mathematics. For nonnegative integers k, d1, . . ., dk, a graph is (d1, . . ., dk)-colorable if its vertex set can be partitioned into k parts so that the ith part induces a graph with maximum degree at most di 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.