Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions

Cited 12 time in webofscience Cited 0 time in scopus
  • Hit : 109
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorKim, Jaehoonko
dc.contributor.authorKostochka, Alexandrko
dc.contributor.authorZhu, Xudingko
dc.date.accessioned2019-07-18T05:34:19Z-
dc.date.available2019-07-18T05:34:19Z-
dc.date.created2019-07-17-
dc.date.created2019-07-17-
dc.date.created2019-07-17-
dc.date.created2019-07-17-
dc.date.issued2016-04-
dc.identifier.citationJOURNAL OF GRAPH THEORY, v.81, no.4, pp.403 - 413-
dc.identifier.issn0364-9024-
dc.identifier.urihttp://hdl.handle.net/10203/263347-
dc.description.abstractA graph G is -colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)-colorable is easy, the similar problem with in place of (0, 0) is NP-complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is -colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all k >= 2 j + 2.(C) 2015 Wiley Periodicals, Inc. J. Graph Theory 81: 403-413, 2016-
dc.languageEnglish-
dc.publisherWILEY-BLACKWELL-
dc.titleImproper Coloring of Sparse Graphs with a Given Girth, II: Constructions-
dc.typeArticle-
dc.identifier.wosid000370183500007-
dc.identifier.scopusid2-s2.0-84958112699-
dc.type.rimsART-
dc.citation.volume81-
dc.citation.issue4-
dc.citation.beginningpage403-
dc.citation.endingpage413-
dc.citation.publicationnameJOURNAL OF GRAPH THEORY-
dc.identifier.doi10.1002/jgt.21886-
dc.contributor.localauthorKim, Jaehoon-
dc.contributor.nonIdAuthorKostochka, Alexandr-
dc.contributor.nonIdAuthorZhu, Xuding-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorimproper coloring-
dc.subject.keywordAuthordefective coloring-
dc.subject.keywordAuthorsparse graph-
dc.subject.keywordAuthorgirth-
dc.subject.keywordPlusSET-
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 12 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0