List vertex arboricity of planar graphs without 5-cycles intersecting with 6-cycles

Yanping Yang; Yang Wang; Juan Liu; Yanping Yang; Yang Wang; Juan Liu

doi:10.3934/math.2021567

AIMS Mathematics

2021, Volume 6, Issue 9: 9757-9769. doi: 10.3934/math.2021567

Previous Article Next Article

Research article

List vertex arboricity of planar graphs without 5-cycles intersecting with 6-cycles

1.
Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China
2.
School of Science, East China Jiaotong University, Nanchang 330013, China

Received: 11 January 2021 Accepted: 08 June 2021 Published: 28 June 2021
MSC : 05C15

The vertex arboricity $ a(G) $ of a graph $ G $ is the minimum number of colors required to color the vertices of $ G $ such that no cycle is monochromatic. The list vertex arboricity $ a_l(G) $ is the list version of this concept. In this paper, we prove that if $ G $ is a planar graph without 5-cycles intersecting with 6-cycles, then $ a_l(G)\le 2 $.
- planar graph,
- list vertex arboricity,
- intersecting cycles
Citation: Yanping Yang, Yang Wang, Juan Liu. List vertex arboricity of planar graphs without 5-cycles intersecting with 6-cycles[J]. AIMS Mathematics, 2021, 6(9): 9757-9769. doi: 10.3934/math.2021567

Related Papers:

Abstract

The vertex arboricity $ a(G) $ of a graph $ G $ is the minimum number of colors required to color the vertices of $ G $ such that no cycle is monochromatic. The list vertex arboricity $ a_l(G) $ is the list version of this concept. In this paper, we prove that if $ G $ is a planar graph without 5-cycles intersecting with 6-cycles, then $ a_l(G)\le 2 $.

References

[1]	O. V. Borodin, A. O. Ivanova, Planar graphs without $4$-cycles adjacent to $3$-cycles are list vertex $2$-arborable, J. Graph Theory, 62 (2009), 234–240. doi: 10.1002/jgt.20394
[2]	G. Chartrand, H. V. Kronk, C. E. Wall, The point-arboricity of a graph, Israel J. Math., 6 (1968), 169–175. doi: 10.1007/BF02760181
[3]	M. Chen, A. Raspaud, W. F. Wang, Vertex-arboricity of planar graphs without intersecting triangles, Eur. J. Combin., 33 (2012), 905–923. doi: 10.1016/j.ejc.2011.09.017
[4]	M. Chen, L. Huang, W. F. Wang, List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles, Discrete Math., 339 (2016), 2526–2535. doi: 10.1016/j.disc.2016.04.010
[5]	I. Choi, H. H. Zhang, Vertex arboricity of toroidal graphs with a forbidden cycle, Discrete Math., 333 (2014), 101–105. doi: 10.1016/j.disc.2014.06.011
[6]	S. L. Hakimi, E. F. Schmeichel, A note on the vertex arboricity of a graph, SIAM J. Discrete Math., 2 (1989), 64–67. doi: 10.1137/0402007
[7]	D. J. Huang, W. C. Shiu, W. F. Wang, On the vertex-arboricity of planar graphs without $7$-cycles, Discrete Math., 312 (2012), 2304–2315. doi: 10.1016/j.disc.2012.03.035
[8]	L. Huang, M. Chen, W. F. Wang, Toroidal graphs without 3-cycles adjacent to 5-cycles have list vertex-arboricity at most 2, Int. J. Math. Stat., 16 (2015), 97–105.
[9]	W. F. Wang, L. Huang, M. Chen, List vertex-arboricity of planar graphs without intersecting $5$-cycles, Acta Math. Appl. Sin. Engl. Ser., 36 (2020), 439–447. doi: 10.1007/s10255-020-0936-1
[10]	A. Raspaud, W. F. Wang, On the vertex-arboricty of planar graphs, Eur. J. Combin., 29 (2008), 1064–1075. doi: 10.1016/j.ejc.2007.11.022
[11]	Y. Q. Wang, M. Chen, W. F. Wang, A note on the list vertex arboricity of toroidal graphs, Discrete Math., 341 (2018), 3344–3347. doi: 10.1016/j.disc.2018.08.021
[12]	Y. P. Yang, Y. Q. Wang, P. Wang, W. F. Wang, List vertex arboricity of planar graphs of diameter two, Adv. Math. (China), 50 (2021), 335–344.
[13]	A. F. Yang, J. J. Yuan, On the vertex arboricity of planar graphs of diameter two, Discrete Math., 307 (2007), 2438–2447. doi: 10.1016/j.disc.2006.10.017
[14]	H. Zhang, On list vertex 2-arboricity of toroidal graphs without cycles of specific length, Bull. Iranian Math. Soc., 42 (2016), 1293–1303.

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)