DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, Ilkyoo | ko |
dc.contributor.author | Liu, Chun-Hung | ko |
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2018-08-20T06:50:21Z | - |
dc.date.available | 2018-08-20T06:50:21Z | - |
dc.date.created | 2018-06-12 | - |
dc.date.created | 2018-06-12 | - |
dc.date.created | 2018-06-12 | - |
dc.date.issued | 2018-06 | - |
dc.identifier.citation | SIAM JOURNAL ON DISCRETE MATHEMATICS, v.32, no.2, pp.1209 - 1228 | - |
dc.identifier.issn | 0895-4801 | - |
dc.identifier.uri | http://hdl.handle.net/10203/244693 | - |
dc.description.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 is an element of{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. | - |
dc.language | English | - |
dc.publisher | SIAM PUBLICATIONS | - |
dc.title | CHARACTERIZATION OF CYCLE OBSTRUCTION SETS FOR IMPROPER COLORING PLANAR GRAPHS | - |
dc.type | Article | - |
dc.identifier.wosid | 000436975900023 | - |
dc.identifier.scopusid | 2-s2.0-85049603321 | - |
dc.type.rims | ART | - |
dc.citation.volume | 32 | - |
dc.citation.issue | 2 | - |
dc.citation.beginningpage | 1209 | - |
dc.citation.endingpage | 1228 | - |
dc.citation.publicationname | SIAM JOURNAL ON DISCRETE MATHEMATICS | - |
dc.identifier.doi | 10.1137/16M1106882 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.contributor.nonIdAuthor | Choi, Ilkyoo | - |
dc.contributor.nonIdAuthor | Liu, Chun-Hung | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | graph coloring | - |
dc.subject.keywordAuthor | improper coloring | - |
dc.subject.keywordAuthor | defective coloring | - |
dc.subject.keywordAuthor | planar graphs | - |
dc.subject.keywordAuthor | obstruction sets | - |
dc.subject.keywordPlus | SPARSE GRAPHS | - |
dc.subject.keywordPlus | GIRTH | - |
dc.subject.keywordPlus | MAP | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.