Halin图的邻和可区别边染色与边权点染色

摘要：

记[k]=[1,2,…,k],称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndiΣ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndiΣ(G)≤△(G)+2,并证明了任一Halin图是4-边权可染的.

关键词：Halin图、邻和可区别边染色、边权点染色

所属期刊栏目：45

资助基金：国家自然科学基金青年基金11301134,11301135,河北省自然科学基金A2012202067

在线出版日期：2015-04-13（万方平台首次上网日期，不代表论文的发表时间）

页码：294-298