List \(r\)-dynamic coloring of sparse graphs (Q2309401): Difference between revisions

An \(r\)-dynamic coloring of a graph \(G\) is a proper coloring of the vertices of \(G\) such that the neighbors of every vertex receive either at least \(r\) colors or all different colors. The \(r\)-dynamic chromatic number of \(G\), denoted \(\chi_r(G)\) is the minimum number of colors required in an \(r\)-dynamic coloring of \(G\). The list \(r\)-dynamic chromatic number of a graph \(G\), denoted \(\operatorname{ch}_r(G)\), is the list version of the \(r\)-dynamic chromatic number; in other words, each vertex has its own set of possible colors instead of a universal color set. This article proves the following three results regarding the list \(r\)-dynamic chromatic number of a graph \(G\): \par if \(G\) is planar with girth at least \(5\), then \(\operatorname{ch}_r(G)\leq r+5\) for \(r\geq 15\), \par if mad\((G)<\frac{10}{3}\), then \(\operatorname{ch}_r(G)\leq r+10\), \par if mad\((G)<\frac{8}{3}\), then \(\operatorname{ch}_r(G)\leq r+1\) for \(r\geq 14\). The proofs utilize the popular discharing method.