-
摘要: 运用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:
- planar graphedge coloringmaximum degreeClass 1 /
点击查看大图
计量
- 文章访问数: 2990
- HTML全文浏览量: 34
- PDF下载量: 1083
- 被引次数: 0