Neighbor Sum Distinguishing Edge Coloring of Subcubic Graphs  

作　　者：Xiao Wei YU Guang Hui WANG Jian Liang WU Gui Ying YAN 

机构地区：[1]School of Mathematics,Shandong University [2]School of Mathematics,Academy of Mathematics and System Sciences,Chinese Academy of Sciences

出　　处：《Acta Mathematica Sinica,English Series》2017年第2期252-262,共11页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant Nos.11371355,11471193,11271006,11631014);the Foundation for Distinguished Young Scholars of Shandong Province(Grant No.JQ201501);the Fundamental Research Funds of Shandong University and Independent Innovation Foundation of Shandong University(Grant No.IFYT14012)

摘　　要：A proper edge-k-coloring of a graph G is a mapping from E（G） to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E（G）, the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let X（G ） denote the smallest value k in such a ＇ G coloring of G. This parameter makes sense for graphs containing no isolated edges （we call such graphs normal）. The maximum average degree mad（G） of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad（G） 〈 5 then x＇（G） ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.A proper edge-k-coloring of a graph G is a mapping from E（G） to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E（G）, the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let X（G ） denote the smallest value k in such a ＇ G coloring of G. This parameter makes sense for graphs containing no isolated edges （we call such graphs normal）. The maximum average degree mad（G） of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad（G） 〈 5 then x＇（G） ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.

关 键 词：Proper edge coloring neighbor sum distinguishing edge coloring maximum average de-gree subcubic graph planar graph 

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