Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs

Cited 26 time in webofscience Cited 22 time in scopus
  • Hit : 203
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorKim, Jaehoonko
dc.contributor.authorKostochka, Alexandrko
dc.contributor.authorZhu, Xudingko
dc.date.accessioned2019-07-18T05:34:23Z-
dc.date.available2019-07-18T05:34:23Z-
dc.date.created2019-07-17-
dc.date.created2019-07-17-
dc.date.created2019-07-17-
dc.date.issued2014-11-
dc.identifier.citationEUROPEAN JOURNAL OF COMBINATORICS, v.42, pp.26 - 48-
dc.identifier.issn0195-6698-
dc.identifier.urihttp://hdl.handle.net/10203/263349-
dc.description.abstractA graph G is (0, 1)-colorable if V (G) can be partitioned into two sets V-0 and V-1 so that G[V-0] is an independent set and G[V-1] has maximum degree at most I. The problem of verifying whether a graph is (0, 1)-colorable is NP-complete even in the class of planar graphs of girth 9. The maximum average degree, mad(G), of a graph G is the maximum of 2 vertical bar E(H)vertical bar/vertical bar V(H)vertical bar over all subgraphs H of G. It was proved recently that every graph G with mad(G) <= 12/5 is (0, 1)-colorable, and this is sharp. This yields that every planar graph with girth at least 12 is (0, 1)-colorable. Let F(g) denote the supremum of a such that for some constant b(g) every graph G with girth g and vertical bar E(H)vertical bar <= a vertical bar V(H)vertical bar b(g) for every H subset of G is (0, 1)-colorable. By the above, F(3) = 1.2. We find the exact value for F(4) and F(5): F(4) = F(5) = 11/9. In fact, we also find the best possible values of b(4) and b(5): every triangle-free graph G with vertical bar E(H)vertical bar < 11 vertical bar V(H)vertical bar+5/9 for every H subset of G is (0, 1)-colorable, and there are infinitely many not (0, 1)-colorable graphs G with girth 5, vertical bar E(G)vertical bar = 11 vertical bar V(G)vertical bar+5/9 and vertical bar E(H)vertical bar < 11 vertical bar V(H)vertical bar+5/9 for every proper subgraph H of G. A corollary of our result is that every planar graph of girth 11 is (0, 1)-colorable. This answers a half of a question by Dorbec, Kaiser, Montassier and Raspaud. In a companion paper, we show that for every g, F(g) <= 1.25 and resolve some similar problems for the so-called (j, k)-colorings generalizing (0, 1)-colorings. (C) 2014 Elsevier Ltd. All rights reserved.-
dc.languageEnglish-
dc.publisherACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD-
dc.titleImproper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs-
dc.typeArticle-
dc.identifier.wosid000341464700003-
dc.identifier.scopusid2-s2.0-84902489215-
dc.type.rimsART-
dc.citation.volume42-
dc.citation.beginningpage26-
dc.citation.endingpage48-
dc.citation.publicationnameEUROPEAN JOURNAL OF COMBINATORICS-
dc.identifier.doi10.1016/j.ejc.2014.05.003-
dc.contributor.localauthorKim, Jaehoon-
dc.contributor.nonIdAuthorKostochka, Alexandr-
dc.contributor.nonIdAuthorZhu, Xuding-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
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 26 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0