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

Cited 12 time in webofscience Cited 0 time in scopus
  • Hit : 102
  • Download : 0
A 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
Publisher
WILEY-BLACKWELL
Issue Date
2016-04
Language
English
Article Type
Article
Citation

JOURNAL OF GRAPH THEORY, v.81, no.4, pp.403 - 413

ISSN
0364-9024
DOI
10.1002/jgt.21886
URI
http://hdl.handle.net/10203/263347
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