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

《山东大学学报(理学版)》 ›› 2018, Vol. 53 ›› Issue (12): 31-40.doi: 10.6040/j.issn.1671-9352.0.2017.642

• • 上一篇    下一篇

不含4-圈或弦6-圈的平面图是(3,0,0)-可染的

刘佳,孙磊*   

  1. 山东师范大学数学与统计学院, 山东 济南 250014
  • 出版日期:2018-12-20 发布日期:2018-12-18
  • 作者简介:刘佳(1993— ),女, 硕士研究生,研究方向为图论与组合优化. E-mail:793949186@qq.com*通信作者简介:孙磊(1971— ),女,博士,副教授,研究方向为图论与组合优化. E-mail:Lsun@163.com
  • 基金资助:
    国家自然科学基金资助项目(11701342);数学天元基金项目(11626148);山东省自然科学基金青年基金项目(ZR2016AQ01)

Planar graphs without 4-cycle or chordal-6-cycle are(3,0,0)-colorable

LIU Jia, SUN Lei*   

  1. School of Mathematics and statistics, Shandong Normal University, Jinan 250014, Shandong, China
  • Online:2018-12-20 Published:2018-12-18

PDF (PC)

1162

摘要： 设d1,d2,…,dk是k个非负整数,若图G=(V,E)的顶点集V能被剖分成k个子集V1,V2,…,Vk,使得对任意的i=1,2,…,k,Vi的点导出子图G［Vi］的最大度至多为di,则称图G是(d1,d2,…,dk)-可染的。关于平面图的染色,有以下结论:不含4-圈或弦6-圈的平面图是(3,0,0)-可染的。

关键词: 可平面图, 非正常染色, 圈, 弦6-圈

Abstract: Let d1,d2,…,dk be k non-negative intergers. A graph G is(d1,d2,…,dk)-colorable, if the vertex set of G can be partitioned into subsets V1,V2,…,Vk such that the graph G［Vi］ induced by Vi has maximum degree at most di for i=1,2,…,k. There is a conclusion about the coloring of planar graphs: planar graphs without 4-cycle or chordal-6-cycle are(3,0,0)-colorable.

Key words: planar graph, improper coloring, cycle, chordal-6-cycle

中图分类号: 

  • O157.5
[1] APPEL K. Every planar map is four colorable. Part I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21:203-214.
[2] APPEL K, HAKEN W. Every planar map is four colorable. Part Ⅱ: Reducibility[J]. Illinois Journal of Mathematics, 1977, 21:491-567.
[3] GRÖTZSCH H. Zur theorie der diskreten gebilde, vii: ein dreifarbensatz für dreikreisfreie netze auf der kugel[J]. Wiss. Zeitschrift der Martin-Luther-Univ. Halle-Wittenberg, Math.-Nat, 1959, 8:109-120.
[4] COWEN L J, COWEN R H, WOODALL D R. Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valence[J]. Journal of Graph Theory, 1986, 10(2):187-195.
[5] XU B. On(3, 1)*-coloring of plane graphs[J]. Society for Industrial and Applied Mathematics, 2008, 23(1):205-220.
[6] STEINBERG R. The state of the three color problem[J]. Annals of Discrete Mathematics, 1993, 55(8):211-248.
[7] DONG W, XU B. A note on list improper coloring of plane graphs[J]. Discrete Appl Math, 2009, 157:433-436.
[8] CHANG G, HAVET F, MONTASSIER M, et al. Steinbergs conjecture and near-colorings[J]. Chemistry International-Newsmagazine for IUPAC, 2011, 26(2):4-7.
[9] HILL O, SMITH D, WANG Y Q, et al. Planar graphs without cycles of length 4 or 5 are(3,0,0)-colorable[J]. Discrete Mathematics, 2013, 313(20):2312-2317.
[10] HILL O, YU G. A relaxation of Steinbergs conjecture[J/OL]. SIAM J Discrete Math, 27(1):584-596. arXiv:1208.3395v1.http://arxiv.org/abs/1208.3395v1.
[11] XU L, MIAO Z, WANG Y. Every planar graph with cycles of length neither 4 nor 5 is(1,1,0)-colorable[M]. New York: Springer-Verlag, 2014.
[12] 徐灵姬, 王应前. 既不含4-圈又不含6-圈的平面图的非正常染色[J]. 中国科学:数学, 2013, 43(1):15-24. XU Lingji,WANG Yingqian. Improper colorability of planar graphs with cycles of length neither 4 nor 6[J]. Sci Sin Math, 2013, 43:15-24.
[13] LI H, XU J, WANG Y. Planar graphs with cycles of length neither 4 nor 7 are(3,0,0)[J]. Discrete Mathematics, 2014, 327:29-35.
[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): 42-50.
[14] 牛蓓,张欣. 反d-退化图中的点不交3-圈[J]. 《山东大学学报(理学版)》, 2020, 55(9): 51-53.
[15] 马丽丽,李强. δ-李color代数的交换扩张[J]. 《山东大学学报(理学版)》, 2020, 55(8): 38-42.
Viewed
Full text


Abstract

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