平面图的无圈5-可选性
Acyclic 5-Choosability of Planar Graph
DOI: 10.12677/AAM.2023.128351, PDF,   
作者: 傅水苗：浙江师范大学数学科学学院，浙江 金华
关键词: 平面图；无圈染色；无圈可选性；Planar Graph； Acyclic Coloring； Acyclic Choosability
摘要: 假设Φ是图G的一个顶点染色。如果任意两个相邻的点染不同颜色，且每个圈至少使用三种颜色，则称Φ是一个无圈染色。如果对于G的任意的k-列表配置L，G有一个无圈L-染色，则称G是无圈k-可选的。本文证明了3圈不与i(i=3,7,9)圈相邻和4圈不与j(3≤j≤6)圈相邻的平面图是无圈5-可选的。
Abstract: Let Φ is a vertex coloring of graph G. The Φ is acyclic if two adjacent vertices color with different colors and every cycle uses at least three colors. A graph G is k-acyclicallychoosable if G is acyclic L-list colorable for any list assignment L with ▏L(v)▏≥k for each v∈V(G). In this paper, we prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where j=3,7,9 if i=3 and 3≤j≤6 if i=4.
文章引用：傅水苗. 平面图的无圈5-可选性[J]. 应用数学进展, 2023, 12(8): 3530-3536. https://doi.org/10.12677/AAM.2023.128351

参考文献

[1] Grünbaum, B. (1973) Acyclic Colorings of Planar Graphs. Israel Journal of Mathematics, 14, 390-408. [Google Scholar] [CrossRef] 
[2] Borodin, O.V. (1979) On Acyclic Colorings of Planar Graphs. Discrete Mathematics, 25, 211-236. [Google Scholar] [CrossRef] 
[3] Kostochka, A.V. and Mel’nikov, L.S. (1976) Note to the Pa-per of Grünbaum on Acyclic Colorings. Discrete Mathematics, 14, 403-406. [Google Scholar] [CrossRef] 
[4] Voigt, M. (1993) List Colorings of Planar Graph. Discrete Mathematics, 120, 215-219. [Google Scholar] [CrossRef] 
[5] Thomassen, C. (1994) Every Planar Graph Is 5-Choosable. Journal of Combinatorial Theory, Series B, 62, 180-181. [Google Scholar] [CrossRef] 
[6] Borodin, O.V., Fon-Der-Flaass, D.G., Kostochka, A.V., Raspaud, A. and Sopena, E. (2002) Acyclic List 7-Coloring of Planar Graphs. Journal of Graph Theory, 40, 83-90. [Google Scholar] [CrossRef] 
[7] Montassier, M., Ochem, P. and Raspaud, A. (2006) On the Acyclic Choosa-bility of Graphs. Journal of Graph Theory, 51, 281-300. [Google Scholar] [CrossRef] 
[8] Montassier, M., Raspaud, A. and Wang, W. (2007) Acyclic 5-Choosability of Planar Graphs without Small Cycles. Journal of Graph Theory, 54, 245-260. [Google Scholar] [CrossRef] 
[9] Zhang, H. and Xu, B. (2009) Acyclic 5-Choosable Planar Graphs with Neither 4-Cycles nor Chordal 6-Cycles. Discrete Mathematics, 309, 6087-6091. [Google Scholar] [CrossRef] 
[10] Chen, M. and Wang, W. (2008) Acyclic 5-Choosability of Planar Graphs without 4-Cycles. Discrete Mathematics, 308, 6216-6225. [Google Scholar] [CrossRef] 
[11] Borodin, O.V. and Ivanova, A.O. (2011) Acyclic 5-Choosability of Planar Graphs without Adjacent Short Cycles. Journal of Graph Theory, 68, 169-176. [Google Scholar] [CrossRef] 
[12] Borodin, O.V. and Ivanova, A.O. (2013) Acyclic 4-Choosability of Planar Graphs with no 4- and 5-Cycles. Journal of Graph Theory, 72, 374-397. [Google Scholar] [CrossRef] 
[13] Wang, W.F., Zhang, G. and Chen, M. (2014) Acyclic 6-Choosability of Planar Graphs without Adjacent Short Cycles. Science China Mathematics, 57, 197-209. [Google Scholar] [CrossRef] 
[14] Hou, J.F. and Liu, G.Z. (2014) Every Toroidal Graph Is Acycli-cally 8-Choosable. Acta Mathematica Sinica, English Series, 30, 343-352. [Google Scholar] [CrossRef] 
[15] Sun, L. (2021) Acyclic 6-Choosability of Planar Graphs without 5-Cycles and Adjacent 4-Cycles. Acta Mathematica Sinica, English Series, 37, 992-1004. [Google Scholar] [CrossRef] 

为你推荐