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.

Total-coloring of Sparse Graphs with Maximum Degree 6

Given a graph G=(V,E)and a positive integer k,a k-total-coloring of G is a mappingφ:V⋃E→{1,2,⋯,k}such that no two adjacent or incident elements receive the same color.The central problem of the total-colorings is the Total Coloring Conjecture,which asserts that every graph of maximum degreeΔadmits a(Δ+2)-total-coloring.More precisely,this conjecture has been verified forΔ≤5,and it is still open whenΔ=6,even for planar graphs.Let mad(G)denote the maximum average degree of the graph G.In this paper,we prove that every graph G withΔ(G)=6 and mad(G)<23/5 admits an 8-total-coloring.

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.

Upper Bounds on List Star Chromatic Index of Sparse Graphs

A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_(st)(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(G)is defined analogously.The star edge coloring problem is known to be NP-complete,and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear.In this paper,we study,in contrast,the best linear upper bound for sparse graph classes.We show that for everyε>0 there exists a constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.

Backbone Coloring for Triangle-free Planar Graphs

Let G be a graph and H a subgraph of G. A backbone-k-coloring of （G, H） is a mapping f： V（G） → {1,2,…,k} such that If（u）- f（v）｜ ≥ 2 if uv ∈ E（H） and ｜f（u）- f（v） ｜ ≥ 1 if uv ∈ E（G）／E（H）. The backbone chromatic number of （G, H） denoted by Xb（G, H） is the smallest integer k such that （G, H） has a backbone-k-coloring. In this paper, we prove that if G is either a connected triangle-free planar graph or a connected graph with mad（G） 〈 3, then there exists a spanning tree T of G such that Xb（G, T） ≤ 4.

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.