CHARACTERIZATION OF CYCLE OBSTRUCTION SETS FOR IMPROPER COLORING PLANAR GRAPHS.
In: SIAM Journal on Discrete Mathematics, Jg. 32 (2018-06-01), Heft 2, S. 1209-1228
Online
academicJournal
Zugriff:
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. [ABSTRACT FROM AUTHOR]
Titel: |
CHARACTERIZATION OF CYCLE OBSTRUCTION SETS FOR IMPROPER COLORING PLANAR GRAPHS.
|
---|---|
Autor/in / Beteiligte Person: | ILKYOO, CHOI ; CHUN-HUNG, LIU ; SANG-IL, OUM |
Link: | |
Zeitschrift: | SIAM Journal on Discrete Mathematics, Jg. 32 (2018-06-01), Heft 2, S. 1209-1228 |
Veröffentlichung: | 2018 |
Medientyp: | academicJournal |
ISSN: | 0895-4801 (print) |
DOI: | 10.1137/16M1106882 |
Schlagwort: |
|
Sonstiges: |
|