zbMATH — the first resource for mathematics

List 3-dynamic coloring of graphs with small maximum average degree. (English) Zbl 1383.05106
Summary: An \(r\)-dynamic \(k\)-coloring of a graph \(G\) is a proper \(k\)-coloring such that for any vertex \(v\), there are at least \(\min \{r, \deg_G(v) \}\) distinct colors in \(N_G(v)\). The \(r\)-dynamic chromatic number \(\chi_r^d(G)\) of a graph \(G\) is the least \(k\) such that there exists an \(r\)-dynamic \(k\)-coloring of \(G\). The list \(r\)-dynamic chromatic number of a graph \(G\) is denoted by \(\operatorname{ch}_r^d(G)\).
Recently, S. Loeb et al. [Discrete Appl. Math. 235, 129–141 (2018; Zbl 1375.05098)] showed that the list 3-dynamic chromatic number of a planar graph is at most 10. J. Cheng et al. [ibid. 237, 75–81 (2018; Zbl 1380.05056)] studied the maximum average condition to have \(\chi_3^d(G) \leq 4, 5\), or 6. On the other hand, H. Song et al. [ibid. 198, 251–263 (2016; Zbl 1327.05085)] showed that if \(G\) is planar with girth at least 6, then \(\chi_r^d(G) \leq r + 5\) for any \(r \geq 3\).
In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that \(\operatorname{ch}_3^d(G) \leq 6\) if \(\operatorname{mad}(G) < \frac{18}{7}\), \(\operatorname{ch}_3^d(G) \leq 7\) if \(\operatorname{mad}(G) < \frac{14}{5}\), and \(\operatorname{ch}_3^d(G) \leq 8\) if \(\operatorname{mad}(G) < 3\). All of the bounds are tight.

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
Full Text: DOI arXiv
[1] Akbari, S.; Ghanbari, M.; Jahanbekam, S., On the List dynamic coloring of graphs, Discrete Appl. Math., 157, 3005-3007, (2009) · Zbl 1211.05038
[2] J. Cheng, H.-J. Lai, K. Lorenzen, R. Luo, J. Thompson, C.Q. Zhang, r-hued coloring of sparse graphs, manuscript.
[3] Cranston, D.; Kim, S.-J., List-coloring the square of a subcubic grap, J. Graph Theory, 57, 65-87, (2008) · Zbl 1172.05023
[4] Esperet, L., Dynamic List coloring of bipartite graphs, Discrete Appl. Math., 158, 1963-1965, (2010) · Zbl 1215.05062
[5] Havet, F., Choosability of the square of planar subcubic graphs with large girth, Discrete Math., 309, 3553-3563, (2009) · Zbl 1213.05084
[6] Jahanbekam, S.; Kim, J.; O, S.; West, D. B., On r-dynamic coloring of graphs, Discrete Appl. Math., 206, 65-72, (2016) · Zbl 1335.05065
[7] Kang, R.; Müller, T.; West, D. B., On \(r\)-dynamic coloring of grids, Discrete Appl. Math., 186, 286-290, (2015) · Zbl 1311.05066
[8] Kim, S.-J.; Lee, S. J.; Park, W.-J., Dynamic coloring and List dynamic coloring of planar graphs, Discrete Appl. Math., 161, 2207-2212, (2013) · Zbl 1287.05046
[9] J. Kim, S. Ok, Dynamic choosability of triangle-free graphs and sparse random graphs. J. Graph Theory, (in press). · Zbl 1386.05060
[10] Kim, S.-J.; Park, W.-J., List dynamic coloring of sparse graphs, combinatorial optimization and applications, Lecture Notes in Comput. Sci., 6831, 156-162, (2011) · Zbl 1342.05043
[11] S. Loeb, T. Mahoney, B. Reiniger, J. Wise, Dynamic coloring parameters for graphs with given genus, manuscript. · Zbl 1375.05098
[12] Montgomery, B., Dynamic Coloring of Graphs, (2001), West Virginia University, (Ph.D. Thesis)
[13] Song, H.; Fan, S.; Chen, Y.; Sun, L.; Lai, H.-J., On r-hued coloring of \(K_4\)-minor free graphs, Discrete Math., 315, 47-52, (2014) · Zbl 1278.05109
[14] Song, H.; Lai, H.-J.; Wu, J.-L., On \(r\)-hued coloring of planar graphs with girth at least 6, Discrete Appl. Math., 198, 251-263, (2016) · Zbl 1327.05085
[15] G. Wegner, Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, 1977.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.