Characterization of cycle obstruction sets for improper coloring planar graphs

Ilkyoo Choi, Chun Hung Liu, Sang Il Oum

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1209-1228
Number of pages20
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number2
DOIs
StatePublished - Jan 1 2018

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

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

Fingerprint Dive into the research topics of 'Characterization of cycle obstruction sets for improper coloring planar graphs<sup>∗</sup>'. Together they form a unique fingerprint.

Cite this