Neighbor sum distinguishing edge coloring of subcubic graphs |
| |
Authors: | Xiao Wei Yu Guang Hui Wang Jian Liang Wu Gui Ying Yan |
| |
Institution: | 1. School of Mathematics, Shandong University, Ji'nan 250100, P. R. China;
2. School of Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing 10080, P. R. China |
| |
Abstract: | 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. |
| |
Keywords: | Proper edge coloring neighbor sum distinguishing edge coloring maximum average degree subcubic graph planar graph |
本文献已被 CNKI SpringerLink 等数据库收录! |
| 点击此处可从《数学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学学报(英文版)》下载免费的PDF全文 |
|