CHARACTERIZATION OF CYCLE OBSTRUCTION SETS FOR IMPROPER COLORING PLANAR GRAPHS

Cited 1 time in webofscience Cited 0 time in scopus
  • Hit : 131
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorChoi, Ilkyooko
dc.contributor.authorLiu, Chun-Hungko
dc.contributor.authorOum, Sang-ilko
dc.date.accessioned2018-08-20T06:50:21Z-
dc.date.available2018-08-20T06:50:21Z-
dc.date.created2018-06-12-
dc.date.created2018-06-12-
dc.date.created2018-06-12-
dc.date.issued2018-06-
dc.identifier.citationSIAM JOURNAL ON DISCRETE MATHEMATICS, v.32, no.2, pp.1209 - 1228-
dc.identifier.issn0895-4801-
dc.identifier.urihttp://hdl.handle.net/10203/244693-
dc.description.abstractFor 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.languageEnglish-
dc.publisherSIAM PUBLICATIONS-
dc.titleCHARACTERIZATION OF CYCLE OBSTRUCTION SETS FOR IMPROPER COLORING PLANAR GRAPHS-
dc.typeArticle-
dc.identifier.wosid000436975900023-
dc.identifier.scopusid2-s2.0-85049603321-
dc.type.rimsART-
dc.citation.volume32-
dc.citation.issue2-
dc.citation.beginningpage1209-
dc.citation.endingpage1228-
dc.citation.publicationnameSIAM JOURNAL ON DISCRETE MATHEMATICS-
dc.identifier.doi10.1137/16M1106882-
dc.contributor.localauthorOum, Sang-il-
dc.contributor.nonIdAuthorChoi, Ilkyoo-
dc.contributor.nonIdAuthorLiu, Chun-Hung-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorgraph coloring-
dc.subject.keywordAuthorimproper coloring-
dc.subject.keywordAuthordefective coloring-
dc.subject.keywordAuthorplanar graphs-
dc.subject.keywordAuthorobstruction sets-
dc.subject.keywordPlusSPARSE GRAPHS-
dc.subject.keywordPlusGIRTH-
dc.subject.keywordPlusMAP-
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0