华东师范大学学报(自然科学版) ›› 2010, Vol. 2010 ›› Issue (3): 85-91.

• 应用数学与基础数学 • 上一篇    下一篇

最大度是4的可平面图是第一类图的充分条件

倪伟平   

  1. 枣庄学院数学与信息科学系, 山东枣庄 277160
  • 收稿日期:2009-05-31 修回日期:2009-09-09 出版日期:2010-05-25 发布日期:2010-05-25
  • 通讯作者: 倪伟平

Some sufficient conditions for a planar graph of maximum degree four to be Class 1

NI Wei-ping   

  1. Department of Mathematics and Information Science,Zaozhuang University,Zaozhuang Shandong 277160, China
  • Received:2009-05-31 Revised:2009-09-09 Online:2010-05-25 Published:2010-05-25
  • Contact: NI Wei-ping

PDF

1264

摘要： 运用Discharge方法证明: 最大度是4,满足下列条件之一的可平面图G是第一类的.(1)G中不含长度为4至9的圈;(2)G中不含4-圈和5-圈,任意两个3-面不关联于同一个顶点;(3)G中不含长度在5和8之间的圈 且任意两个3-圈,任意两个4-圈不关联于同一个顶点; (4)围长不小于4,G中不含有弦的8-圈 且任意两个4-面不关联于同一个顶点.

关键词: 平面图, 边染色, 最大度, 第一类图, 平面图, 边染色, 最大度, 第一类图

Abstract: By applying discharging method, we showed that a planar graph G with maximum degree four and girth g is of class 1, if it satisfies one of the following conditions. (1) G does not contain cycles of length from 4 to 9; (2) G does not contain 4-cycles and 5-cycles, and two 3-faces are not incident with a common vertex; (3) G does not contain cycles of length from 5 to 8, and two 3-cycles, two 4-cycles are not incident with a common vertex ; (4) g≧geqslant 4, G does not contain chordal-8-cycle, and two 4-faces are not incident with a common vertex.

Key words: edge coloring, maximum degree, Class 1, planar graph, edge coloring, maximum degree, Class 1

中图分类号: