• •

### 无4-圈和5-圈的平面图的k-frugal列表染色

1. 同济大学数学科学学院, 上海 200092
• 收稿日期:2017-12-15 出版日期:2018-10-20 发布日期:2018-10-09
• 作者简介:房启明(1992— ),男,硕士研究生,研究方向为图论. E-mail: fangqiming@tongji.edu.cn*通信作者简介: 张莉(1978— ),女,博士,副教授,硕士生导师,研究方向为图论. E-mail:lizhang@tongji.edu.cn
• 基金资助:
国家自然科学基金资助项目(11201342)

### k-frugal list coloring of planar graphs without 4 and 5-cycles

FANG Qi-ming, ZHANG Li*

1. School of Mathematical Sciences, Tongji University, Shanghai 200092, China
• Received:2017-12-15 Online:2018-10-20 Published:2018-10-09

Abstract: For a graph G, c is a proper vertex coloring of G. If every color appears at most k-1 times in the neighbors of each vertex v, then c is called a k-frugal coloring of G. There are two conclusions on the k-frugal list coloring of planar graphs without 4 and 5-cycles:(1)For each planar graph without 4 and 5-cycles, if its maximum degree is Δ and Δ≥3k+8, then the k-frugal list chromatic number is less than or equal to 「(Δ)/(k-1)+2; (2)For each planar graph without 4 and 5-cycles, its k-frugal list chromatic number is no more than 「(Δ)/(k-1)+5.

Key words: frugal list coloring, planar graph, cycle

• O158
 [1] BONDY J, MURTY U. Graph theory[M]. London: Springer, 2008. [2] HIND H, MOLLOY M, REED B. Colouring a graph frugally[J]. Combinatorica, 1997, 17(4):469-482. [3] YUSTER R. Linear coloring of graphs[J]. Discrete Mathematics, 1998, 185(1-3):293-297. [4] ESPERET L, MONTASSIER M, RASPAUD A. Linear choosability of graphs[J]. Discrete Mathematics, 2015, 308(17):3938-3950. [5] CRANSTON D, YU G. Linear choosability of sparse graphs[J]. Discrete Mathematics, 2010, 311(17):1910-1917. [6] BORODIN O, FONDER F D, KOSTOCHKA A, et al. Acyclic list 7-coloring of planar graphs[J]. Journal of Graph Theory, 2002, 40(2):83-90. [7] COHEN N. Linear and 2-frugal choosability of graphs of small maximum average degree[J]. Graphs & Combinatorics, 2011, 27(6):831-849. [8] ERD″/OS P, RUBIN A, TAYLOR H. Choosability in graphs[C] // West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 1979, 26:125-157. [9] RASPAUD A, WANG W. Linear coloring of planar graphs with large girth[J]. Discrete Mathematics, 2009, 309(18):5678-5686. [10] AMINI O, ESPERET L, HEUVEL J. Frugal colouring of graphs[J/OL]. arXiv: 0705.0422, 2007. http://cn.arxiv.org/abs/0705.0422. [11] STEINBERG R. The state of the three color problem[J]. Annals of Discrete Mathematics, 1993, 55(08):211-248. [12] WANG Deqiang, WEN Yupeng, WANG Kelun. A smaller planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable[J]. Information Processing Letters, 2008, 108(3):87-89. [13] VOIGT M. A non-3-choosable planar graph without cycles of length 4 and 5[J]. Discrete Mathematics, 2007, 307(7):1013-1015.
 [1] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106. [2] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39. [3] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41. [4] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30. [5] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78. [6] 白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报（理学版）, 2016, 51(4): 59-64. [7] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101. [8] 孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报（理学版）, 2015, 50(12): 127-129. [9] 薛丽霞, 李志慧, 谢佳丽. 对3条超边的超圈存取结构最优信息率的一点注记[J]. 山东大学学报（理学版）, 2015, 50(11): 60-66. [10] 王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报（理学版）, 2015, 50(10): 27-31. [11] 孟献青. 一类平面图的强边染色[J]. 山东大学学报（理学版）, 2015, 50(08): 10-13. [12] 张绍华, 颜谨, 李硕. 图中相互独立的4-圈和8-圈[J]. 山东大学学报（理学版）, 2015, 50(02): 1-4. [13] 杨陈, 马海成. 两类特殊三圈图的正负惯性指数和零度[J]. 山东大学学报（理学版）, 2015, 50(02): 32-37. [14] 马刚. 围长不小于11且最大度为3的平面图的#br# 无圈列表边染色[J]. 山东大学学报（理学版）, 2014, 49(2): 18-23. [15] 陈宏宇1, 张丽2. 不含弦5-圈和弦6-圈的平面图的线性2荫度[J]. 山东大学学报（理学版）, 2014, 49(06): 26-30.
Viewed
Full text

Abstract

Cited

Shared
Discussed