DP-3-coloring of planar graphs without certain cycles. (English) Zbl 1462.05145
Summary: DP-coloring is a generalization of list-coloring, which was introduced by Z. Dvořák and L. Postle [J. Comb. Theory, Ser. B 129, 38–54 (2018; Zbl 1379.05034)]. H. Zhang [Inf. Process. Lett. 110, No. 24, 1084–1087 (2010; Zbl 1379.05043)] showed that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is 3-choosable. R. Liu et al. [Discrete Math. 342, No. 1, 178–189 (2019; Zbl 1400.05086)] showed that every planar graph without 4-, 5-, 6- and 9-cycles is DP-3-colorable. In this paper, we show that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is DP-3-colorable, which generalizes these results. Y. Yin and G. Yu [ibid. 342, No. 8, 2333–2341 (2019; Zbl 1418.05059)] gave three Bordeaux-type results by showing that: (i) every planar graph with the distance of triangles at least three and no 4-, 5-cycles is DP-3-colorable; (ii) every planar graph with the distance of triangles at least two and no 4-, 5-, 6-cycles is DP-3-colorable; (iii) every planar graph with the distance of triangles at least two and no 5-, 6-, 7-cycles is DP-3-colorable. We also give two Bordeaux-type results in the last section: (i) every planar graph with neither 5-, 6-, 8-cycles nor triangles at distance less than two is DP-3-colorable; (ii) every planar graph with neither 4-, 5-, 7-cycles nor triangles at distance less than two is DP-3-colorable.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C38 | Paths and cycles |
References:
| [1] | Chen, L.; Liu, R.; Yu, G.; Zhao, R.; Zhou, X., DP-4-colorability of two classes of planar graphs, Discrete Math., 342, 11, 2984-2993 (2019) · Zbl 1419.05068 |
| [2] | Dvořák, Z.; Lidický, B.; Škrekovski, R., Planar graphs without 3-, 7-, and 8-cycles are 3-choosable, Discrete Math., 309, 20, 5899-5904 (2009) · Zbl 1213.05076 |
| [3] | Dvořák, Z.; Lidický, B.; Škrekovski, R., 3-choosability of triangle-free planar graphs with constraints on 4-cycles, SIAM J. Discrete Math., 24, 3, 934-945 (2010) · Zbl 1223.05069 |
| [4] | Dvořák, Z.; Postle, L., Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B, 129, 38-54 (2018) · Zbl 1379.05034 |
| [5] | Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, (Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979). Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, Utilitas Math. (1980), Winnipeg, Man.), 125-157 · Zbl 0469.05032 |
| [6] | Han, Y., A note on 3-choosability of planar graphs, J. Xinjiang Univ. Nat. Sci., 26, 3, 281-283 (2009) · Zbl 1224.05173 |
| [7] | Kim, S.-J.; Ozeki, K., A sufficient condition for DP-4-colorability, Discrete Math., 341, 7, 1983-1986 (2018) · Zbl 1387.05091 |
| [8] | Lam, P. C.B.; Shiu, W. C.; Song, Z. M., The 3-choosability of plane graphs of girth 4, Discrete Math., 294, 3, 297-301 (2005) · Zbl 1062.05061 |
| [9] | Li, X.; Chen, M.; Wang, Y., On 3-choosability of planar graphs without 5-, 6- or 7-cycles, Adv. Math. (China), 45, 4, 491-499 (2016) · Zbl 1374.05070 |
| [10] | R. Li, T. Wang, DP-4-coloring of planar graphs with some restrictions on cycles, arXiv:1909.08511, https://arxiv.org/abs/1909.08511. |
| [11] | Li, X.; Wang, Y., A note on 3-choosability of planar graphs, J. Zhejiang Norm. Univ. Nat. Sci., 39, 1, 13-17 (2016) · Zbl 1363.05050 |
| [12] | Lidický, B., On 3-choosability of plane graphs having no 3-, 6-, 7- and 8-cycles, Australas. J. Combin., 44, 77-86 (2009) · Zbl 1177.05042 |
| [13] | Liu, R.; Li, X., Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable, Discrete Math., 342, 3, 623-627 (2019) · Zbl 1403.05050 |
| [14] | Liu, R.; Li, X., Every planar graph without adjacent cycles of length at most 8 is 3-choosable, European J. Combin., 82, Article 102995 pp. (2019) · Zbl 1423.05072 |
| [15] | Liu, R.; Loeb, S.; Rolek, M.; Yin, Y.; Yu, G., DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{ 6 , 7 , 8 \}\), Graphs Combin., 35, 3, 695-705 (2019) · Zbl 1416.05113 |
| [16] | Liu, R.; Loeb, S.; Yin, Y.; Yu, G., DP-3-coloring of some planar graphs, Discrete Math., 342, 1, 178-189 (2019) · Zbl 1400.05086 |
| [17] | F. Lu, Q. Wang, T. Wang, 3-choosable planar graphs with some precolored vertices and no \(5^-\)-cycles normally adjacent to \(8^-\)-cycles, arXiv:1908.04902v2, https://arxiv.org/abs/1908.04902v2. |
| [18] | F. Lu, Q. Wang, T. Wang, Cover and variable degeneracy, arXiv:1907.06630, https://arxiv.org/abs/1907.06630. |
| [19] | Shen, L.; Wang, Y., A sufficient condition for a planar graph to be 3-choosable, Inform. Process. Lett., 104, 4, 146-151 (2007) · Zbl 1183.05022 |
| [20] | Thomassen, C., \(3\)-list-coloring planar graphs of girth \(5\), J. Combin. Theory Ser. B, 64, 1, 101-107 (1995) · Zbl 0822.05029 |
| [21] | Vizing, V. G., Coloring the vertices of a graph in prescribed colors, Diskret. Analiz., 29, 3-10 (1976), 101 |
| [22] | Wang, Y.; Lu, H.; Chen, M., A note on 3-choosability of planar graphs, Inform. Process. Lett., 105, 5, 206-211 (2008) · Zbl 1183.05023 |
| [23] | Wang, Y.; Lu, H.; Chen, M., Planar graphs without cycles of length 4, 5, 8 or 9 are 3-choosable, Discrete Math., 310, 1, 147-158 (2010) · Zbl 1228.05131 |
| [24] | Wang, Y.; Wu, Q., Planar graphs without cycles of length 4, 5, 8 or 10 are 3-choosable, Adv. Appl. Math. Sci., 10, 3, 297-305 (2011) · Zbl 1283.05113 |
| [25] | Wang, Y.; Wu, Q.; Shen, L., Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable, Discrete Appl. Math., 159, 4, 232-239 (2011) · Zbl 1210.05029 |
| [26] | Yin, Y.; Yu, G., Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable, Discrete Math., 342, 8, 2333-2341 (2019) · Zbl 1418.05059 |
| [27] | Zhang, H., A sufficient condition for a toroidal graph to be 3-choosable, Ars Combin., 105, 193-203 (2012) · Zbl 1274.05184 |
| [28] | Zhang, H., Corrigendum to “On 3-choosability of planar graphs with neither adjacent triangles nor 5-, 6- and 9-cycles” [Information Processing Letters 110 (24) (2010) 1084-1087], Inform. Process. Lett., 113, 354-356 (2013) · Zbl 1287.05032 |
| [29] | Zhang, H., A note on 3-choosability of planar graphs related to Montanssier’s conjecture, Canad. Math. Bull., 59, 2, 440-448 (2016) · Zbl 1337.05045 |
| [30] | Zhang, H.; Sun, Z., On 3-choosability of planar graphs without certain cycles, Inform. Process. Lett., 107, 3-4, 102-106 (2008) · Zbl 1185.05070 |
| [31] | Zhang, L.; Wu, B., Three-choosable planar graphs without certain small cycles, Graph Theory Notes N. Y., 46, 27-30 (2004) |
| [32] | Zhang, L.; Wu, B., A note on 3-choosability of planar graphs without certain cycles, Discrete Math., 297, 1-3, 206-209 (2005) · Zbl 1070.05046 |
| [33] | Zhang, H.; Xu, B., On 3-choosability of plane graphs without 6-, 7- and 9-cycles, Appl. Math. J. Chinese Univ. Ser. B, 19, 1, 109-115 (2004) · Zbl 1045.05047 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
