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

《山东大学学报(理学版)》 ›› 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)

745

摘要： 设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] 李强,马丽丽,王晓燕,吕莉娇. Hom-Jordan李代数的交换扩张[J]. 《山东大学学报(理学版)》, 2018, 53(12): 4-8.
[2] 陈洪玲,王慧娟,高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 《山东大学学报(理学版)》, 2018, 53(12): 17-22.
[3] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[4] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[5] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[6] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[7] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[8] 白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报（理学版）, 2016, 51(4): 59-64.
[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   
[1] 杨军. 金属基纳米材料表征和纳米结构调控[J]. 山东大学学报（理学版）, 2013, 48(1): 1 -22 .
[2] 何海伦， 陈秀兰*. 变性剂和缓冲系统对适冷蛋白酶MCP-01和中温蛋白酶BP-01构象影响的圆二色光谱分析何海伦， 陈秀兰*[J]. 山东大学学报（理学版）, 2013, 48(1): 23 -29 .
[3] 赵君1,赵晶2,樊廷俊1*,袁文鹏1,3,张铮1,丛日山1. 水溶性海星皂苷的分离纯化及其抗肿瘤活性研究[J]. J4, 2013, 48(1): 30 -35 .
[4] 孙小婷1,靳岚2*. DOSY在寡糖混合物分析中的应用[J]. J4, 2013, 48(1): 43 -45 .
[5] 罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .
[6] 杨伦，徐正刚，王慧*，陈其美，陈伟，胡艳霞，石元，祝洪磊，曾勇庆*. RNA干扰沉默PID1基因在C2C12细胞中表达的研究[J]. J4, 2013, 48(1): 36 -42 .
[7] 冒爱琴1, 2, 杨明君2, 3, 俞海云2, 张品1, 潘仁明1*. 五氟乙烷灭火剂高温热解机理研究[J]. J4, 2013, 48(1): 51 -55 .
[8] 杨莹,江龙*,索新丽. 容度空间上保费泛函的Choquet积分表示及相关性质[J]. J4, 2013, 48(1): 78 -82 .
[9] 李永明1, 丁立旺2. PA误差下半参数回归模型估计的r-阶矩相合[J]. J4, 2013, 48(1): 83 -88 .
[10] 杨永伟1,2,贺鹏飞2,李毅君2,3. BL-代数的严格滤子[J]. 山东大学学报（理学版）, 2014, 49(03): 63 -67 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发