## Abstract

For nonnegative integers k, d_{1}, . . ., d_{k}, a graph is (d_{1}, . . ., d_{k})-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_{i} 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1209-1228 |

Number of pages | 20 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 32 |

Issue number | 2 |

DOIs | |

State | Published - 2018 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Keywords

- Defective coloring
- Graph coloring
- Improper coloring
- Obstruction sets
- Planar graphs