Neighbor sum distinguishing edge coloring of subcubic graphs

详细信息    查看全文

• 作者：Xiao Wei Yu ; Guang Hui Wang ; Jian Liang Wu…
• 关键词：Proper edge coloring ; neighbor sum distinguishing edge coloring ; maximum average degree ; subcubic graph ; planar graph
• 刊名：Acta Mathematica Sinica, English Series
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：33
• 期：2
• 页码：252-262
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics, general;
• 出版者：Institute of Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society
• ISSN：1439-7617
• 卷排序：33

文摘

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 fromthe sumof colors taken on the edges incident to v. Let χ′_Σ(G) denote the smallest value k in such a 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/2, then χ′_Σ(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.