Dynamic coloring parameters for graphs with given genus

作者：Loeb Sarah; Mahoney Thomas; Reiniger Benjamin^*; Wise Jennifer

来源：Discrete Applied Mathematics, 2018, 235: 129-141.

DOI：10.1016/j.dam.2017.09.013

• r-dynamic coloring
• r-dynamic paintability
• Graph genus

A proper vertex coloring of a graph G is r-dynamic if for each v is an element of V(G), at least min{r, d(v)} colors appear in N-G(v). In this paper we investigate r-dynamic versions of coloring, list coloring, and paintability. We prove that planar and toroidal graphs are 3-dynamically 10 colorable, and this bound is sharp for toroidal graphs. We also give bounds on the minimum number of colors needed for any r in terms of the genus of the graph: for sufficiently large r, every graph with genus g is r-dynamically ((r + 1)(g + 5) + 3)-colorable when g <= 2 and r-dynamically ((r + 1)(2g + 2) + 3)-colorable when g >= 3. Furthermore, each of these upper bounds for r-dynamic k-colorability also holds for r-dynamic k-choosability and for r-dynamic k-paintability.

• 出版日期2018-1-30