zbMATH — the first resource for mathematics

Dynamic choosability of triangle-free graphs and sparse random graphs. (English) Zbl 1386.05060
Summary: The $$r$$-dynamic choosability of a graph $$G$$, written $$\mathrm{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\}$$ neighbors of distinct colors. Let $$\mathrm{ch}(G)$$ denote the choice number of $$G$$. In this article, we prove $$\mathrm{ch}_r(G)\leq(1+o(1))\mathrm{ch}(G)$$ when $$\frac{\Delta(G)}{\delta(G)}$$ is bounded. We also show that there exists a constant $$C$$ such that the random graph $$G=G(n,p)$$ with $$\frac{6\log(n)}n<p\leq\frac12$$ almost surely satisfies $$\mathrm{ch}_2(G)\leq\mathrm{ch}(G)+C$$. Also if $$G$$ is a triangle-free regular graph, then we have $$\mathrm{ch}_2(G)\leq\mathrm{ch}(G)+86$$.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C42 Density (toughness, etc.) 05C80 Random graphs (graph-theoretic aspects)
Full Text: