Neighbor Sum Distinguishing Edge Coloring of Subcubic Graphs

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.

Neighbor Sum Distinguishing Index of Graphs with Maximum Average Degree

A proper k-edge coloring of a graph G = (V(G), E(G)) is an assignment c: E(G) → {1, 2, …, k} such that no two adjacent edges receive the same color. A neighbor sum distinguishing k-edge coloring of G is a proper k-edge coloring of G such that for each edge uv ∈ E(G). The neighbor sum distinguishing index of a graph G is the least integer k such that G has such a coloring, denoted by χ’Σ(G). Let be the maximum average degree of G. In this paper, we prove χ’Σ(G) ≤ max{9, Δ(G) +1} for any normal graph G with . Our approach is based on the discharging method and Combinatorial Nullstellensatz.

Neighbor Sum Distinguishing Chromatic Index of Sparse Graphs via the Combinatorial Nullstellensatz

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 ∑eЭu Ф（e）≠∑eЭu Ф（e） 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{（2｜E（H）｜）/（｜V（H）｜）｜HЭG}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-2/（△（G））, then χ＇Σ（G）≤△（G） ＋ 1. This improves the previous results and the bound △（G） ＋ 1 is sharp.

Neighbor Sum Distinguishing Index of Sparse Graphs

A proper k-edge coloring of a graph G is an assignment of one of k colors to each edge of G such that there are no two edges with the same color incident to a common vertex.Let f(v)denote the sum of colors of the edges incident to v.A k-neighbor sum distinguishing edge coloring of G is a proper k-edge coloring of G such that for each edge uv∈E(G),f(u)≠f(v).Byχ’_∑(G),we denote the smallest value k in such a coloring of G.Let mad(G)denote the maximum average degree of a graph G.In this paper,we prove that every normal graph with mad(G)<10/3 andΔ(G)≥8 admits a(Δ(G)+2)-neighbor sum distinguishing edge coloring.Our approach is based on the Combinatorial Nullstellensatz and discharging method.