Dynamic choosability of triangle-free graphs and sparse random graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 86
  • Download : 0
Ther-dynamic choosability of a graph G, written ch(r) (G), is the least k such that whenever each vertex is assigned a list of at least k colors a proper coloring can be chosen from the lists so that every vertex v has at least min{d(G) (v), r} neigh-bors of distinct colors. Let ch(G) denote the choice number of G. In this article, we prove ch(r)(G) <= (1 + o(1)) ch(G) when Delta(G)/delta(G) is bounded. We also show that there exists a constant.. such that the random graph G = G (n, p) with 6log(n)/n < p <= 1/2 almost surely ch(2()G) <= ch(G) + C. Also if G is a triangle-free regular graph, then we have ch(2()G) <= ch(G) + 86.
Publisher
WILEY
Issue Date
2018-03
Language
English
Article Type
Article
Citation

JOURNAL OF GRAPH THEORY, v.87, no.3, pp.347 - 355

ISSN
0364-9024
DOI
10.1002/jgt.22161
URI
http://hdl.handle.net/10203/263341
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0