平面图的强边染色的一个结果  

A Result on the Strong Edge Coloring of Planar Graphs

作　　者：张埂[1] 扈丁文 古华华 

机构地区：[1]四川文理学院学报编辑部,四川达州635000 [2]达县第四中学,四川达州635000

出　　处：《西昌学院学报（自然科学版）》2012年第1期66-67,72,共3页Journal of Xichang University(Natural Science Edition)

基　　金：四川文理学院2011年院级科研项目(项目编号:2011Z008Y)

摘　　要：如果图G的一个正常边染色的任意有公共邻边的两条边的染色不相同,则它是图G的一个强边染色。图G的强边染色所需要的最小颜色数称作图G的强边色数。本文利用差值转移方法证明了最大顶点度为偶数且不小于6的平面图,如果其不含有3圈,则其强边色数不超过5△2/4,特别地,本文证明了最大顶点度为4的平面图,如果其围长不小于5,则其强边色数不超过20。For a proper edge coloring of a simple graphG,if any two edges which are adjacent to a same edge have different colors,then,it is a strong edge coloring of G.The minimum number of colors of any strong edge colorings of G is the strong chromatic number of G.In this paper,by using discharging method,we proved that the strong chromatic number for planar graphs with even maximum degree which is at least 6 and without 3 cycles is no more than 5Δ~2/4,furthermore,we proved that 20 is an upper bound of the strong chromatic number of planar graphs with maximum degree 4 and girth at least 5.

关 键 词：强边染色 差值转移法 强边色数 

分 类 号：O157.5[理学—数学]