An improved upper bound for the dynamic list coloring of 1-planar graphs

Xiaoxue Hu; Jiangxu Kong; Xiaoxue Hu; Jiangxu Kong

doi:10.3934/math.2022409

AIMS Mathematics

2022, Volume 7, Issue 5: 7337-7348. doi: 10.3934/math.2022409

Previous Article Next Article

Research article

An improved upper bound for the dynamic list coloring of 1-planar graphs

Xiaoxue Hu ¹,
Jiangxu Kong ^{2
,
,}

1.
School of Science, Zhejiang University of Science & Technology, Hangzhou 310023, China
2.
School of Science, China Jiliang University, Hangzhou 310018, China

Received: 15 September 2021 Revised: 22 January 2022 Accepted: 27 January 2022 Published: 10 February 2022
MSC : 05C10, 05C15

A graph is $ 1 $-planar if it can be drawn in the plane such that each of its edges is crossed at most once. A dynamic coloring of a graph $ G $ is a proper vertex coloring such that for each vertex of degree at least 2, its neighbors receive at least two different colors. The list dynamic chromatic number $ ch_{d}(G) $ of $ G $ is the least number $ k $ such that for any assignment of $ k $-element lists to the vertices of $ G $, there is a dynamic coloring of $ G $ where the color on each vertex is chosen from its list. In this paper, we show that if $ G $ is a 1-planar graph, then $ ch_{d}(G)\leq 10 $. This improves a result by Zhang and Li ^[16], which says that every 1-planar graph $ G $ has $ ch_{d}(G)\leq 11 $.
- 1-planar graph,
- dynamic coloring,
- list coloring
Citation: Xiaoxue Hu, Jiangxu Kong. An improved upper bound for the dynamic list coloring of 1-planar graphs[J]. AIMS Mathematics, 2022, 7(5): 7337-7348. doi: 10.3934/math.2022409

Related Papers:

Abstract

A graph is $ 1 $-planar if it can be drawn in the plane such that each of its edges is crossed at most once. A dynamic coloring of a graph $ G $ is a proper vertex coloring such that for each vertex of degree at least 2, its neighbors receive at least two different colors. The list dynamic chromatic number $ ch_{d}(G) $ of $ G $ is the least number $ k $ such that for any assignment of $ k $-element lists to the vertices of $ G $, there is a dynamic coloring of $ G $ where the color on each vertex is chosen from its list. In this paper, we show that if $ G $ is a 1-planar graph, then $ ch_{d}(G)\leq 10 $. This improves a result by Zhang and Li ^[16], which says that every 1-planar graph $ G $ has $ ch_{d}(G)\leq 11 $.

References

[1]	A. Ahadi, S. Akbari, A. Dehghan, M. Ghanbari, On the difference between chromatic number and dynamic chromatic number of graphs, Discrete Math., 312 (2012), 2579–2583. https://doi.org/10.1016/j.disc.2011.09.006 doi: 10.1016/j.disc.2011.09.006
[2]	M. Alishahi, On the dynamic coloring of graphs, Discrete Appl. Math., 159 (2011), 152–156. https://doi.org/10.1016/j.dam.2010.10.012 doi: 10.1016/j.dam.2010.10.012
[3]	P. Borowiecki, E. Sidorowicz, Dynamic coloring of graphs, Fund. Inform., 114 (2012), 105–128. https://doi.org/10.3233/FI-2012-620 doi: 10.3233/FI-2012-620
[4]	N. Bowler, J. Erde, F. Lehner, M. Merker, M. Pitz, K. Stavropoulos, A counterexample to montgomery's conjecture on dynamic colourings of regular graphs, Discrete Appl. Math., 229 (2017), 151–153. https://doi.org/10.1016/j.dam.2017.05.004 doi: 10.1016/j.dam.2017.05.004
[5]	Y. Chen, S. Fan, H. J. Lai, H. Song, L. Sun, On dynamic coloring for planar graphs and graphs of higher genus, Discrete Appl. Math., 160 (2012), 1064–1071. https://doi.org/10.1016/j.dam.2012.01.012 doi: 10.1016/j.dam.2012.01.012
[6]	L. Esperet, Dynamic list coloring of bipartite graphs, Discrete Appl. Math., 158 (2010), 1963–1965. https://doi.org/10.1016/j.dam.2010.08.007 doi: 10.1016/j.dam.2010.08.007
[7]	D. Karpov, Dynamic proper colorings of a graph, J. Math. Sci., 179 (2011), 601–615. https://doi.org/10.1007/s10958-011-0612-3 doi: 10.1007/s10958-011-0612-3
[8]	Y. Kim, S. Lee, S. Oum, Dynamic coloring of graphs having no $K_5$ minor, Discrete Appl. Math., 206 (2016), 81–89. https://doi.org/10.1016/j.dam.2016.01.022 doi: 10.1016/j.dam.2016.01.022
[9]	S. J. Kim, S. Lee, W. J. Park, Dynamic coloring and list dynamic coloring of planar graphs, Discrete Appl. Math., 161 (2013), 2207–2212. https://doi.org/10.1016/j.dam.2013.03.005 doi: 10.1016/j.dam.2013.03.005
[10]	H. J. Lai, J. Lin, B. Montgomery, T. Shuib, S. Fan, Conditional colorings of graphs, Discrete Math., 306 (2006), 1997–2004. https://doi.org/10.1016/j.disc.2006.03.052 doi: 10.1016/j.disc.2006.03.052
[11]	S. Loeb, T. Mahoney, B. Reiniger, J. Wise, Dynamic coloring parameters for graphs with given genus, Discrete Appl. Math., 235 (2018), 129–141. https://doi.org/10.1016/j.dam.2017.09.013 doi: 10.1016/j.dam.2017.09.013
[12]	B. Montgomery, Dynamic coloring of graphs, West Virginia University, 2001.
[13]	S. Saqaeeyan, E. Mollaahamdi, Dynamic chromatic number of bipartite graphs, Sci. Ann. Comput. Sci., 26 (2016), 249–261. https://doi.org/10.7561/SACS.2016.2.249 doi: 10.7561/SACS.2016.2.249
[14]	N. Vlasova, D. Karpov, Bounds on the dynamic chromatic number of a graph in terms of its chromatic number, J. Math. Sci., 232 (2018), 21–24. https://doi.org/10.1007/s10958-018-3855-4 doi: 10.1007/s10958-018-3855-4
[15]	X. Zhang, J. Wu, On edge coloring of 1-planar graphs, Inform. Process. Lett., 111 (2011), 124–128. https://doi.org/10.1016/j.ipl.2010.11.001 doi: 10.1016/j.ipl.2010.11.001
[16]	X. Zhang, Y. Li, Dynamic list coloring of 1-planar graphs, Discrete Math., 344 (2021), 112333. https://doi.org/10.1016/j.disc.2021.112333 doi: 10.1016/j.disc.2021.112333

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)