无K_4-图子式的图的邻和可区别边染色  

Neighbor Sum Distinguishing Edge Colorings of K_4-minor Free Graphs

作　　者：潘文华[1] 徐常青 

机构地区：[1]河北工业大学理学院,天津300401 [2]河北省大数据计算重点实验室,天津300401

出　　处：《数学进展》2017年第6期839-847,共9页Advances in Mathematics（China）

基　　金：国家自然科学基金青年基金(No.11301134;No.11301135);河北省自然科学基金(No.A2015202301);河北省高等学校科学技术研究重点项目(No.ZD2015106)

摘　　要：给定图G的一个正常k-边染色φ:E(G)→{1,2,…,k},记f(v)是与点v相关联的边的颜色的加和.若对G的每条边uv都有f(u)≠f(v),则称φ是图G的k-邻和可区别边染色.图G存在k-邻和可区别边染色的k的最小值称为图G的邻和可区别边色数,记作χ'_Σ(G).运用组合零点定理研究了△≥6的无K_(4-)图子式的图的邻和可区别边色数,证得若G不含相邻最大度点,则χ'_Σ(G)=△,否则χ'_Σ(G)=△+1.Given a proper k-edge coloring Ф：E（G）→{1,2,…,k）} of graph G, let f（v） be the sum of colors on the edges incident with v.Ф is called a k-neighbor sum distinguishing edge coloring if f（u）≠ f（v） for each edge uv∈ E（G）. The smallest k such that G has a k-neighbor sum distinguishing edge coloring is called the neighbor sum distinguishing index, denoted by χ＇∑ （G）. In this paper, by using Combinatorial Nullstellensatz we study the neighbor sum distinguishing index of K4-minor free graphs with △≥6, and get that if G has no adjacent vertices of maximum degree, then χ＇∑（G） = △, otherwise, χ＇∑（G）=△＋1.

关 键 词：邻和可区别边染色 组合零点定理 无K4-图子式的图 

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