Planar graphs without $ \{4, 6, 8\} $-cycles are 3-choosable

Yueying Zhao; Lianying Miao; Yueying Zhao; Lianying Miao

doi:10.3934/math.2021593

AIMS Mathematics

2021, Volume 6, Issue 9: 10253-10265. doi: 10.3934/math.2021593

Previous Article Next Article

Research article

Planar graphs without $ \{4, 6, 8\} $-cycles are 3-choosable

Yueying Zhao ^1,2,
Lianying Miao ^{1
,
,}

1.
School of Mathematics, China University of Mining and Technology, Xuzhou, Jiangsu, 221116, China
2.
School of Mathematics and Statistics, Xuzhou University of Technology, Xuzhou, Jiangsu, 221000, China

Received: 09 May 2021 Accepted: 07 July 2021 Published: 12 July 2021
MSC : 05C15

In 2018, Dvořák and Postle introduced DP-coloring and proved that planar graphs without cycles of lengths 4 to 8 are 3-choosable. In this paper, we prove that planar graphs without $ \{4, 6, 8\} $-cycles are 3-choosable by using the technique developed in DP-coloring, which also extends the result of Wang and Chen [Sci. China Math., 50 (2007), 1552-1562].
- planar graph,
- DP-coloring,
- 3-choosable
Citation: Yueying Zhao, Lianying Miao. Planar graphs without $ \{4, 6, 8\} $-cycles are 3-choosable[J]. AIMS Mathematics, 2021, 6(9): 10253-10265. doi: 10.3934/math.2021593

Related Papers:

Abstract

In 2018, Dvořák and Postle introduced DP-coloring and proved that planar graphs without cycles of lengths 4 to 8 are 3-choosable. In this paper, we prove that planar graphs without $ \{4, 6, 8\} $-cycles are 3-choosable by using the technique developed in DP-coloring, which also extends the result of Wang and Chen [Sci. China Math., 50 (2007), 1552-1562].

References

[1]	H. Grötzsch, Ein dreifarbensatz fur dreikreisfreie netze auf der kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math. Nat. Reihe, 8 (1959), 109–120.
[2]	R. Steinberg, The state of the three color problem, Ann. Discrete Math., 55 (1993), 211–248. doi: 10.1016/S0167-5060(08)70391-1
[3]	O. V. Borodin, A. N. Glebov, A. Raspaud, M. R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B, 93 (2005), 303–311. doi: 10.1016/j.jctb.2004.11.001
[4]	W. F. Wang, M. Chen, Planar graphs without 4, 6, 8-cycles are 3-colorable, Sci. China Math., 50 (2007), 1552–1562.
[5]	I. Choi, G. X. Yu, X. Zhang, Planar graphs with girth at least 5 are (3, 4)-colorable, Discrete Math., 342 (2019), 111577. doi: 10.1016/j.disc.2019.06.033
[6]	M. Li, X. Zhang, Relaxed equitable colorings of planar graphs with girth at least 8, Discrete Math., 343 (2020), 111790. doi: 10.1016/j.disc.2019.111790
[7]	V. G. Vizing, Vertex coloring with given colors, Metody Diskret. Analiz., 29 (1976), 3–10.
[8]	P. Erdös, A. L. Rubin, H. Talor, Choosability in graphs, Congr. Numer., 26 (1979), 125–157.
[9]	C. Thomassen, 3-list-coloring planar graphs of girth 5, J. Combin. Theory Ser. B, 64 (1995), 101–107. doi: 10.1006/jctb.1995.1027
[10]	Z. Dvořák, 3-choosability of planar graphs with($\geq$4)-cycles far apart, J. Combin. Theory Ser. B, 104 (2014), 28–59. doi: 10.1016/j.jctb.2013.10.004
[11]	Z. Dvořák, L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of length 4 to 8, J. Combin. Theory Ser. B, 129 (2018), 38–54. doi: 10.1016/j.jctb.2017.09.001
[12]	R. R. Liu, X. W. Li, Every planar graph without adjacent cycles of length at most 8 is 3-choosable, European J. Combin., 82 (2019), 102995. doi: 10.1016/j.ejc.2019.07.006
[13]	A. Bernshteyn, The asymptotic behavior of the correspondence chromatic number, Discrete Math., 339 (2016), 2680–2692. doi: 10.1016/j.disc.2016.05.012
[14]	A. Bernshteyn, A. Kostochka, Sharp Dirac's theorem for DP-critical graphs, J. Graph Theory, 88 (2018), 521–546. doi: 10.1002/jgt.22227
[15]	A. Bernshteyn, A. Kostochka, X. D. Zhu, DP-colorings of graphs with high chromatic number, European J. Combin., 65 (2017), 122–129. doi: 10.1016/j.ejc.2017.05.007
[16]	A. Bernshteyn, A. Kostochka, On differences between DP-coloring and list coloring, Sib. Adv. Math., 21 (2018), 61–71.
[17]	A. Bernshteyn, A. Kostochka, S. Pron, On DP-coloring of graphs and multigraphs, Sib. Math. J., 58 (2017), 28–36. doi: 10.1134/S0037446617010049
[18]	R. R. Liu, S. Loeb, M. Rolek, Y. X. Yin, G. X. Yu, DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from $\{6; 7; 8\}$, Graphs Combin., 35 (2019), 695–705. doi: 10.1007/s00373-019-02025-2
[19]	R. R. Liu, S. Loeb, Y. X. Yin, G. X. Yu, DP-3-coloring of some planar graphs, Discrete Math., 342 (2019), 178–189. doi: 10.1016/j.disc.2018.09.025
[20]	Y. X. Yin, G. X. Yu, Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable, Discrete Math., 342 (2019), 2333–2341. doi: 10.1016/j.disc.2019.05.014
[21]	S. Kim, K. Ozeki, A sufficient condition for DP-4-colorability, Discrete Math., 341 (2018), 1983–1986. doi: 10.1016/j.disc.2018.03.027
[22]	L. L. Chen, R. R. Liu, G. X. Yu, R. Zhao, X. Q. Zhou, DP-4-colorability of two classes of planar graphs, Discrete Math., 342 (2019), 2984–2993. doi: 10.1016/j.disc.2019.05.032
[23]	R. R. Liu, X. W. Li, K. Nakprasit, P. Sittitrai, G. X. Yu, DP-4-colorability of planar graphs without adjacent cycles of given length, Discrete Appl. Math., 277 (2020), 245–251. doi: 10.1016/j.dam.2019.09.012

Reader Comments

Your name:*

Email:*
© 2021 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)