应用数学学报
首页  |  期刊介绍  |  编 委 会  |  投稿指南  |  期刊订阅  |  广告服务  |  相关链接  |  下载中心  |  联系我们  |  留言板
 
应用数学学报 英文版  
   
   
高级检索 »  
应用数学学报  2013, Vol. 36 Issue (2): 280-292    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索  |   
最大度为8不含特定子图的平面图的全染色
蔡建生1, 王光辉2, 闫桂英3
1. 潍坊学院数学与信息科学学院, 潍坊, 261061;
2. 山东大学数学学院, 济南, 250100;
3. 中国科学院数学与系统科学研究院, 北京, 100190
Total Coloring of Planar Graph with Maximum Degree 8 and without Specified Subgraph
CAI Jiansheng1, WANG Ganghui2, YAN Guiying3
1. School of Mathematics and Information Science, Weifang University, Weifang, 261061;
2. School of Mathematics, Shandong University, Jinan, 250100;
3. Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing, 100190
 全文: PDF (365 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 全染色是对图G的顶点和边同时进行正常染色, 至少要用Δ+1个色才能对图G进行正常全染色. 本文运用权转移的方法, 证明了最大度为8的不含特定子 图的简单平面图是9-全可染的.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
蔡建生
王光辉
闫桂英
关键词简单图   平面图   全染色   最大度   特定子图     
Abstract: Total-coloring of graph G is to color the vertices and the edges of the graph properly. To this end, we must use at least Δ+1 colors to color the graph properly. In this paper, we use discharging method to verify that every simple planar graph with maximum degree 8 and without specified subgraph is 9-totally colorable.
Key wordssimple graph   planar graph   total coloring   maximum degree   specified subgraph   
收稿日期: 2012-01-09;
基金资助:国家自然科学基金(11001055,71071090);山东省自然科学基金(ZR2009AM009)资助项目.
引用本文:   
蔡建生,王光辉,闫桂英. 最大度为8不含特定子图的平面图的全染色[J]. 应用数学学报, 2013, 36(2): 280-292.
CAI Jiansheng,WANG Ganghui,YAN Guiying. Total Coloring of Planar Graph with Maximum Degree 8 and without Specified Subgraph[J]. Acta Mathematicae Applicatae Sinica, 2013, 36(2): 280-292.
 
[1] Behzad M. Graphs and their Chromatic Numbers, Doctoral Thesis, Michigan State University, 1965
[2] Vizing V G. Some Unsolved Problems in Graph Theory. Uspekhi Mat. Nauk, 1968, 23: 117-134 (in Russian)
[3] Kostochka A V. The Total Chromatic Number of any Multigraph with Maximum Degree Five is at Most Seven. Discrete Math., 1996, 162: 199-214
[4] Sanders D P, Zhao Y. On Total 9-coloring Planar Graphs of Maximum Degree Seven. J. Graph Theory, 1999, 31: 67-73 3.0.CO;2-C target="_blank">
[5] Borodin O V. On the Total Coloring of Planar Graphs. J. Reine Angew. Math., 1989, 394: 180-185
[6] Kowalik L, Sereni J, Skrekovski R. Total-coloring of Plane Graphs with Maximum Degree Nine. Siam J. Discrete Math., 2008, 22: 1462-1479
[7] Shen L, Wang Y. Total Colorings of Planar Graphs with Maximum Degree at Least 8. Sci. China Ser. A, 2009, 52: 1733-1742
[8] Du D, Shen L, Wang Y. Planar Graphs with Maximum Degree 8 and without Adjacent Triangles are 9-totally-colorable. Discrete Appl. Math., 2009, 157: 2778-2784
[9] Borodin O V, Kostochka A, Woodall D. Total Coloring of Planar Graphs with Large Maximum Degree. J. Graph Theory, 1997, 26: 53-59 3.0.CO;2-G target="_blank">
[10] Hou J, Zhu Y, Liu G, Wu J, Lan M. Total Colorings of Planar Graphs without Small Cycles. Graphs Combin, 2008, 24: 91-100
[11] Hou J, Liu B, Liu G, Wu J. Total Coloring of Planar Graphs without 6-cycles. Discrete Appl. Math., 2011, 159: 157-163
[12] Liu B, Hou J, Wu J, Liu G. Total Colorings and List Total Colorings of Planar Graphs without Intersecting 4-cycles. Discrete Math., 2009, 309: 6035-6043
[1] 强会英, 李沐春, 张忠辅. 距离限制下的点可区别全色数的一个上界[J]. 应用数学学报, 2011, 34(3): 554-559.
[2] 马刚, 马少仙, 张忠辅. 一些联图的均匀全染色[J]. 应用数学学报, 2010, 33(4): 624-631.
[3] 闫晓霞91), 李建湘. 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[4] 徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
[5] 刘林忠, 张忠辅, 王建方. 一些平面图的边连结数[J]. 应用数学学报, 2001, 17(4): 443-448.
[6] 刘林忠, 张忠辅, 王建方. 一些平面图的边连结数[J]. 应用数学学报, 2001, 17(4): 443-448.
[7] 王维凡, 张克民. △-匹配与边面全色数[J]. 应用数学学报, 1999, 22(2): 236-242.
[8] 谢力同. 极大外平面图在边界条件下的4染色[J]. 应用数学学报, 1998, 21(1): 0-0.
[9] 于濂, 刘彦佩. 关于3-正则子图问题的一个注记[J]. 应用数学学报, 1995, 18(2): 176-178.
  版权所有 © 2009 应用数学学报编辑部   E-mail: amas@amt.ac.cn
京ICP备05002806号-9