不含相邻三角形平面图的全群可选性
Total Group Choosability of Planar Graphs without Adjacent Triangles
DOI: 10.12677/PM.2023.136172, PDF,    科研立项经费支持
作者: 张 帆, 刘静茹, 常 建*：内蒙古师范大学，内蒙古自治区数学与应用数学中心，内蒙古 呼和浩特
关键词: 平面图；圈；全群可选性；全群选择数；Planar Graphs； Cycle； Total Group Choosability； Total Group Choice Number
摘要: 如果对于阶数至少为k的阿贝尔群A和任意k列表分配L:V→2A，G都是(A,L)可染的，则称图G是k群可选的。G的群选择数是使得G是k群可选的数k的最小值。图G的全图T(G)的群选择数称为G的全群选择数。本文主要研究平面图的全群列表染色，利用结构分析法和Discharging方法，得到了两类不含相邻三角形的特殊平面图的全群选择数的上界。
Abstract: If for any group A of order at least k and any k-list assignment L:V→2A, G is (A,L)-colorable, then we say that G is k-group choosable. The group choice number of G is the smallest k such that G is k-group choosable. The group choice number of the total graph T(G) of the graph G is called the total group choice number of G. In this paper, we mainly study the total group list coloring of planar graphs. By using the structural analysis and the Discharging method, we obtained upper bounds on the number of total group choices for two classes of special planar graphs without adjacent triangles.
文章引用：张帆, 刘静茹, 常建. 不含相邻三角形平面图的全群可选性[J]. 理论数学, 2023, 13(6): 1689-1695. https://doi.org/10.12677/PM.2023.136172

参考文献

[1] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. MacMillan, London.
[2] Erdös, P., Rubin, A.L. and Taylor, H. (1979) Choosability in Graphs. Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, 5-7 September 1979, 125-157.
[3] Hou, J., Liu, G. and Cai, J. (2006) List Edge and List Total Colorings of Planar Graphs without 4-Cycles. Theoretical Computer Science, 369, 250-255. [Google Scholar] [CrossRef] 
[4] 许洋, 朱晓颖, 陈藏. 关于Reed列表染色猜想的一些结果[J]. 纯粹数学与应用数学, 2006, 22(4): 556-559+564.
[5] 董爱君, 李国君, 邹青松. 含相邻三角形的平面图的列表边和列表全染色[J]. 山东大学学报(理学版), 2009, 44(10): 17-20.
[6] Li, R. and Xu, B. (2011) Edge Choosability and Total Choosability of Planar Graphs with No 3-Cycles Adjacent 4-Cycles. Discrete Mathematics, 311, 2158-2163. [Google Scholar] [CrossRef] 
[7] Wang, H., Liu, B., Zhang, X., et al. (2016) List Edge and List Total Coloring of Planar Graphs with Maximum Degree 8. Journal of Combinatorial Optimization, 32, 188-197. [Google Scholar] [CrossRef] 
[8] Wang, Y. and Wang, W. (2022) List-Edge and List-Total Col-orings of Graphs Embedded on Surfaces of Negative Euler Characteristic. In: Srivastava, H.M. and Chen, C.-H., Eds., 2nd International Conference on Applied Mathematics, Modelling, and Intelligent Computing (CAMMIC 2022), Vol. 12259, SPIE, Bellingham, 148-153. [Google Scholar] [CrossRef] 
[9] Jaeger, F., Linial, N., Payan, C. and Tarsi, M. (1992) Group Connectivity of Graphs—A Nonhomogeneous Analogue of Nowhere-Zero Flow Properties. Journal of Combinatorial Theory, Series B, 56, 165-182. [Google Scholar] [CrossRef] 
[10] Král’, D. and Nejedlý, P. (2004) Group Coloring and List Group Coloring Are Π2P-Complete. In: Fiala, J., Koubek, V. and Kratochvíl, J., Eds., Mathematical Foundations of Computer Science 2004. MFCS 2004. Lecture Notes in Computer Science, Vol. 3153, Springer, Berlin, 274-286. [Google Scholar] [CrossRef] 
[11] Omidi, G.R. (2011) A Note on Group Choosability of Graphs with Girth at Least 4. Graphs and Combinatorics, 27, 269-273. [Google Scholar] [CrossRef] 
[12] Chuang, H., Lai, H.-J., Omidi, G.R., Wang, K. and Zakeri, N. (2014) On Group Choosability of Graphs, II. Graphs and Combinatorics, 30, 549-563. [Google Scholar] [CrossRef] 
[13] Zhang, X. and Liu, G.Z. (2013) Group Edge Choosability of Planar Graphs without Adjacent Short Cycles. Acta Mathematica Sinica, English Series, 29, 2079-2086. [Google Scholar] [CrossRef] 
[14] Khamseh, A. (2015) Edge Group Choosability of Planar Graphs with Maximum Degree at Least 11. Proceedings of the 46th Annual Iranian Mathematical Conferences, Yazd, 25-28 August 2015.
[15] Khamseh, A. (2020) A Note on Edge-Group Choosability of Planar Graphs without 5-Cycles. Journal of Mathematics, 2020, Article ID: 4639260. [Google Scholar] [CrossRef] 
[16] Lai, H.J., Omidi, G.R. and Raeisi, G. (2013) On Group Choosability of Total Graphs. Graphs and Combinatorics, 29, 585-597. [Google Scholar] [CrossRef] 

为你推荐