Smarandachely Adjacent-vertex-distinguishing Proper Edge Coloring ofK4 ∨ Kn

Let f be a proper edge coloring of G using k colors.For each x∈V(G),the set of the colors appearing on the edges incident with x is denoted by S_f(x)or simply S(x)if no confusion arise.If S(u)■S(v)and S(v)■S(u)for any two adjacent vertices u and v,then f is called a Smarandachely adjacent vertex distinguishing proper edge coloring using k colors,or k-SA-edge coloring.The minimum number k for which G has a Smarandachely adjacent-vertex-distinguishing proper edge coloring using k colors is called the Smarandachely adjacent-vertex-distinguishing proper edge chromatic number,or SAedge chromatic number for short,and denoted byχ'_(sa)(G).In this paper,we have discussed the SA-edge chromatic number of K_4∨K_n.

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 Colorings of Graphs with Maximum Average Degree Less Than 37/12

Let G be a graph and let its maxiraum degree and maximum average degree be denoted by △（G） and mad（G）, respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E（G）, the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by X∑ （G）. Flandrin et al. proposed the following conjecture that X＇∑ （G） ≤△ （G） ＋ 2 for any connected graph with at least 3 vertices and G ≠ C5. In this paper, we prove that the conjecture holds for a normal graph with mad（G） 〈 37/12and △ （G）≥ 7.

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 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.

A Note on Star Chromatic Number of Graphs

A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored. The star chromatic number of an undirected graph G, denoted by xs（G）, is the smallest integer k for which G admits a star coloring with k colors. In this paper, we show that if G is a graph with maximum degree A, then xs（G） ≤ [7△3/2]], which gets better bound than those of Fertin, Raspaud and Reed.

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.