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\).

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