Dynamic choosability of triangle-free graphs and sparse random graphs

被引:2
作者
Kim, Jaehoon [1 ]
Ok, Seongmin [2 ]
机构
[1] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England
[2] Korea Inst Adv Study, Sch Computat Sci, Seoul 02455, South Korea
基金
新加坡国家研究基金会; 欧洲研究理事会;
关键词
dynamic choosability; dynamic coloring; dynamic list coloring; strong coloring; CHROMATIC NUMBER;
D O I
10.1002/jgt.22161
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:347 / 355
页数:9
相关论文
共 15 条
  • [1] On the difference between chromatic number and dynamic chromatic number of graphs
    Ahadi, A.
    Akbari, S.
    Dehghan, A.
    Ghanbari, M.
    [J]. DISCRETE MATHEMATICS, 2012, 312 (17) : 2579 - 2583
  • [2] Akbari S, 2010, CONTEMP MATH, V531, P11
  • [3] On the list dynamic coloring of graphs
    Akbari, S.
    Ghanbari, M.
    Jahanbekam, S.
    [J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (14) : 3005 - 3007
  • [4] Dynamic chromatic number of regular graphs
    Alishahi, Meysam
    [J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (15) : 2098 - 2103
  • [5] List coloring of random and pseudo-random graphs
    Alon, N
    Krivelevich, M
    Sudakov, B
    [J]. COMBINATORICA, 1999, 19 (04) : 453 - 472
  • [6] Alon N., 1993, Surv. Comb., V187, P1
  • [7] Bowler N., ARXIV170200973
  • [8] Dynamic list coloring of bipartite graphs
    Esperet, Louis
    [J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (17) : 1963 - 1965
  • [9] Haxell P, 2010, ELECTRON J COMB, V17
  • [10] On r-dynamic coloring of graphs
    Jahanbekam, Sogol
    Kim, Jaehoon
    Suil, O.
    West, Douglas B.
    [J]. DISCRETE APPLIED MATHEMATICS, 2016, 206 : 65 - 72