应用数学学报
首页  |  期刊介绍  |  编 委 会  |  投稿指南  |  期刊订阅  |  广告服务  |  相关链接  |  下载中心  |  联系我们  |  留言板
 
应用数学学报 英文版  
   
   
高级检索 »  
应用数学学报  2013, Vol. 36 Issue (6): 988-999    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索  |   
最大度为8且无4-扇的平面图的9-全可染性
李慧慧, 王应前
浙江师范大学数理与信息工程学院, 金华 321004
On the Total 9-colorability of Plane Graphs with Maximum Degree 8 without 4-fans
LI Huihui, WANG Yingqian
College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004
 全文: PDF (414 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 设G=(VE)是一个以V为顶点集,E为边集的图. 图G的一个k-全染色是一个映射φVE→{1,2,…,k}使得 φ(x)≠φ(y) 对所有相邻或相关联的元素xy都成立. 若G有一个k-全染色,则说Gk-全可染的. 令Δ为G的最大度. 显然,对G进行全染色,至少需要Δ+1个颜色. Behzad和Vizing相互独立地猜想每个(简单)图都是(Δ+2)-全可染的. 已知最大度Δ≥9的平面图是 (Δ+1)-全可染的. 通过研究极小反例的新的可约性质,本文运用权转移方法证明了最大度为8且不含4-扇的平面图是9-全可染的,这里的4-扇是指交于一点的4个相继的3-面. 这一结果改进了若干同类型的相关结果.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
李慧慧
王应前
关键词平面图   全染色   最大度        
Abstract: Let G=(V,E) be a graph with sets of vertices and edges V and E, respectively. A total k-coloring of G is a mapping φ: VE→{1,2,…,k} such that φ(x)≠φ(y) whenever x and y are two adjacent or incident elements of VE. G is totally k-colorable if it admits a total k-coloring. Let Δ denote the maximum degree of G. Clearly, at least Δ+1 colors are needed to totally color G. Behzad and Vizing independently conjectured that every graph is totally (Δ+2)-colorable. It is known that plane graphs with maximum degree Δ≥q9 are totally (Δ+1)-colorable. By exploring new reducibility of minimal counterexample, we use discharging method to prove that plane graphs with maximum degree 8 and without 4-fans are totally 9-colorable, where a k-fan in a plane graph consists of k consecutive 3-faces intersecting at a vertex. This improves some known results on the topic of total 9-colorability of plane graphs with maximum degree 8.
Key wordsPlane graphs   total coloring   maximum degree   fan   
收稿日期: 2013-03-31;
基金资助:国家自然科学基金资助项目(11271335).
引用本文:   
李慧慧,王应前. 最大度为8且无4-扇的平面图的9-全可染性[J]. 应用数学学报, 2013, 36(6): 988-999.
LI Huihui,WANG Yingqian. On the Total 9-colorability of Plane Graphs with Maximum Degree 8 without 4-fans[J]. Acta Mathematicae Applicatae Sinica, 2013, 36(6): 988-999.
 
[1] Bondy J A, Murty U S R. Graph Theory. Berlin: Springer-Verlag, 2008
[2] Vizing V G. Some Unsolved Problems in Graph Theory. Uspekhi Mat. Nauk., 1968, 23: 117-134 (in Russian)
[3] Behzad M. Graphs and their Chromatic Numbers. MI: Michigan State University, 1965
[4] Borodin O V, Kostochka A V, Woodall D R. Total Coloring of Planar Graphs with Large Maximum Degree. J. Graph Theory, 1997, 26: 53-59 3.0.CO;2-G target="_blank">
[5] Wang W F. Total Chromatic Number of Planar Graphs with Maximum Degree Ten. J. Graph Theory, 2007, 54: 91-102
[6] Kowalik L, Sereni J S, Škrekovski R. Total Coloring of Plane Graphs with Maximum Degree Nine. SIAM J. Discrete Math., 2008, 22: 1462-1479
[7] Hou J F, Liu G Z, Cai J S. List Edge and List Total Coloring of Planar Graphs without 4-cycles. Theoretical Computer Sci., 2006, 369: 250-255
[8] Hou J F, Zhu Y, Liu G Z, Wu J L, L M. Total Coloring of Planar Graphs without Small Cycles. J. Graphs Comb., 2008, 24: 91-100
[9] Shen L, Wang Y Q. Total Coloring of Planar Graphs with Maximum Degree at Least 8. Science in China Series A, 2009, 52: 1733-1742
[10] Shen L, Wang Y Q, Wang W F, Lih K W. On the 9-total-colorability of Planar Graphs with Maximum Degree at Least 8 and without Intersecting Triangles. Appl. Math. Lett., 2009, 22: 1369-1373
[11] Du D Z, Shen L, Wang Y Q. Planar Graphs with Maximum Degree 8 and without Adjacent Triangles are 9-totally-colorable. Discrete Appl. Math., 2009, 157: 2778-2784
[12] Cai J S, Wang G H, Yan G Y. Planar Graphs with Maximum Degree 8 and without Intersecting Chordal 4-cycles are 9-totally-colorable. Sci. China Math., 2012, 55: 2601-2612
[13] Chang J, Wang H J, Wu J L, A Y G. Total Colorings of Planar Graphs with Maximum Degree 8 and without 5-cycles with Two Chords. Theoretical Computer Science, 2013, 476: 16-23
[14] Sanders D P, Zhao Y. On the 9-coloring Planar Graphs of Maximum Degree Seven. J Graph Theory, 1999, 31: 67-73 3.0.CO;2-C target="_blank">
[15] Wang B, Wu J L. Total Colorings of Planar Graphs with Maximum Degree Seven and without Intersecting 3-cycles. Discrete Math., 2011, 311: 2052-2030
[1] 蔡建生, 王光辉, 闫桂英. 最大度为8不含特定子图的平面图的全染色[J]. 应用数学学报, 2013, 36(2): 280-292.
[2] 强会英, 李沐春, 张忠辅. 距离限制下的点可区别全色数的一个上界[J]. 应用数学学报, 2011, 34(3): 554-559.
[3] 马刚, 马少仙, 张忠辅. 一些联图的均匀全染色[J]. 应用数学学报, 2010, 33(4): 624-631.
[4] 闫晓霞91), 李建湘. 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[5] 徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
[6] 刘林忠, 张忠辅, 王建方. 一些平面图的边连结数[J]. 应用数学学报, 2001, 17(4): 443-448.
[7] 刘林忠, 张忠辅, 王建方. 一些平面图的边连结数[J]. 应用数学学报, 2001, 17(4): 443-448.
[8] 杨启贵. 广义Lienard系统的同宿轨族的存在性[J]. 应用数学学报, 1999, 22(3): 353-361.
[9] 王维凡, 张克民. △-匹配与边面全色数[J]. 应用数学学报, 1999, 22(2): 236-242.
[10] 谢力同. 极大外平面图在边界条件下的4染色[J]. 应用数学学报, 1998, 21(1): 0-0.
[11] 于濂, 刘彦佩. 关于3-正则子图问题的一个注记[J]. 应用数学学报, 1995, 18(2): 176-178.
  版权所有 © 2009 应用数学学报编辑部   E-mail: amas@amt.ac.cn
京ICP备05002806号-9