Neighbor sum distinguishing chromatic index of sparse graphs via the combinatorial Nullstellensatz |
| |
Authors: | Xiao-wei?Yu Yu-ping?Gao Email author" target="_blank">Lai-hao?DingEmail author |
| |
Institution: | 1.School of Mathematics,Shandong University,Jinan,China |
| |
Abstract: | Let ?: E(G) → {1, 2, · · ·, k} be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if \(\sum\limits_{e \mathrel\backepsilon u} {\phi \left( e \right)} \ne \sum\limits_{e \mathrel\backepsilon v} {\phi \left( e \right)} \) for each edge uv ∈ E(G). The smallest value k for which G has such a coloring is denoted by χ′Σ(G), which makes sense for graphs containing no isolated edge (we call such graphs normal). It was conjectured by Flandrin et al. that χ′Σ(G) ≤ Δ(G) + 2 for all normal graphs, except for C5. Let mad(G) = \(\max \left\{ {\frac{{2\left| {E\left( h \right)} \right|}}{{\left| {V\left( H \right)} \right|}}|H \subseteq G} \right\}\) be the maximum average degree of G. In this paper, we prove that if G is a normal graph with Δ(G) ≥ 5 and mad(G) < 3 ? \(\frac{2}{{\Delta \left( G \right)}}\), then χ′Σ(G) ≤ Δ(G) + 1. This improves the previous results and the bound Δ(G) + 1 is sharp. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|