您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2018, Vol. 53 ›› Issue (10): 35-41.doi: 10.6040/j.issn.1671-9352.0.2017.648

• • 上一篇    下一篇

无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

PDF (PC)

1319

摘要： 在图G的一个正常点染色c中,对于图中任意一点v,如果每种颜色在点v的邻点中至多出现k-1次,这个染色就称为图G的一个k-frugal染色。关于无4-圈和5-圈的平面图的k-frugal列表染色问题,有以下两个结论:(1)对于一切不含4-圈和5-圈的平面图,如果其最大度满足Δ≥3k+8,其k-frugal列表色数小于等于「Δ/(k-1)+2;(2)一切不含4-圈和5-圈的平面图,则其k-frugal列表色数小于等于「Δ/(k-1)+5。

关键词: 平面图, 圈, frugal列表染色

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] 王辉,刘蒙蒙. 三圈图的Mostar指标的下界[J]. 《山东大学学报(理学版)》, 2025, 60(8): 68-77.
[2] 白羽,强会英,何静. 联图Cm∨Cn的邻和可区别边染色[J]. 《山东大学学报(理学版)》, 2025, 60(12): 161-166.
[3] 王丽,李敬文,杨文珠,裴华艳. 单圈图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2024, 59(6): 44-55.
[4] 常景智,杨超,姚兵. 关于图的邻和可区别全染色的新方法[J]. 《山东大学学报(理学版)》, 2023, 58(6): 35-39.
[5] 李锦,徐常青. 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2023, 58(12): 134-139.
[6] 邓梓健,刘彬,火博丰. 一类均匀拟阵的二阶圈图连通性及哈密顿性[J]. 《山东大学学报(理学版)》, 2022, 57(5): 92-96.
[7] 谭钧铭,强会英,王洪申. 单圈图的邻和可区别边染色[J]. 《山东大学学报(理学版)》, 2022, 57(2): 78-83.
[8] 索孟鸽,陈京荣,张娟敏. 笛卡尔乘积图的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2022, 57(12): 103-110.
[9] 马丽丽,吴迪,李强,许晶. 关于Hom-δ-Jordan李三系的交换扩张[J]. 《山东大学学报(理学版)》, 2022, 57(10): 1-5.
[10] 马丽丽,戴迪,李强. δ-Jordan李超三系的构造和交换扩张[J]. 《山东大学学报(理学版)》, 2021, 56(8): 76-80.
[11] 谭香. 一类最大度为6的平面图的全染色[J]. 《山东大学学报(理学版)》, 2021, 56(11): 71-75.
[12] 杨晗,陈祥恩. mC7的点可区别Ⅰ-全染色和Ⅵ-全染色[J]. 《山东大学学报(理学版)》, 2021, 56(11): 76-82.
[13] 刘卓雅,徐常青. 无相交三角形平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2020, 55(9): 36-41.
[14] 王笔美,李敬文,顾彦波,邵淑宏. 单圈图的边幻和全标号[J]. 《山东大学学报(理学版)》, 2020, 55(9): 42-50.
[15] 牛蓓,张欣. 反d-退化图中的点不交3-圈[J]. 《山东大学学报(理学版)》, 2020, 55(9): 51-53.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发