# Graphs with Bounded Maximum Average Degree and Their Neighbor Sum Distinguishing Total-Choice Numbers

Authors: Patcharapan Jumnongnit; Kittikorn Nakprasit
Journal: International Journal of Mathematics and Mathematical Sciences
 (2017)

---

## Abstract

LetG be a graph and ϕ:V(G)∪E(G)→{1,2,3,…,k} be a k-total coloring. Let w(v) denote the sum of color on a vertex v and colors assigned to edges incident to v. If w(u)≠w(v) whenever uv∈E(G), then ϕ is called a neighbor sum distinguishing total coloring. The smallest integer k such that G has a neighbor sum distinguishing k-total coloring is denoted by tndi∑(G). In 2014, Dong and Wang obtained the results about tndi∑(G) depending on the value of maximum average degree. A k-assignment L of G is a list assignment L of integers to vertices and edges with L(v)=k for each vertex v and L(e)=k for each edge e. Atotal-L-coloring is a total coloring ϕ of G such that ϕ(v)∈L(v) whenever v∈V(G) and ϕ(e)∈L(e) whenever e∈E(G). We state that G has aneighbor sum distinguishing total-L-coloring if G has a total-L-coloring such that w(u)≠w(v) for all uv∈E(G). The smallest integer k such that G has a neighbor sum distinguishing total-L-coloring for every k-assignment L is denoted by Ch∑′′(G). In this paper, we strengthen results by Dong and Wang by giving analogous results for Ch∑′′(G).


---

## Body

## 1. Introduction

LetG be a simple, finite, and undirected graph. We use V(G), E(G), and Δ(G) to denote the vertex set, edge set, and maximum degree of a graph G, respectively. A vertex v is called a k-vertex if d(v)=k. The length of a shortest cycle in G is called thegirth of a graph G, denoted by g(G). Themaximum average degree of G is defined by mad(G)=maxH⊆G(2EH/VH). The well-known observation for a planar graph G is mad(G)<2g(G)/(g(G)-2). Let ϕ:V(G)∪E(G)→{1,2,3,…,k} be a k-total coloring. We denote the sum (set, resp.) of colors assigned to edges incident to v and the color on the vertex v by w(v) (C(v), resp.); that is, w(v)=∑uv∈E(G)‍ϕ(uv)+ϕ(v) and C(v)={ϕ(v)}∪{ϕ(uv)∣uv∈E(G)}. The total coloring ϕ of G is aneighbor sum distinguishing (neighbor distinguishing, resp.) total coloring if w(u)≠w(v) (C(u)≠C(v), resp.) for each edge uv∈E(G). The smallest integer k such that G has a neighbor sum distinguishing (neighbor distinguishing, resp.) total coloring is called theneighbor sum distinguishing total chromatic number (neighbor distinguishing total chromatic number, resp.), denoted by tndi∑(G) (tndi(G), resp.). In 2005, a neighbor distinguishing total coloring of graphs was introduced by Zhang et al. [1]. They obtained tndi(G) for many basic graphs and brought forward the following conjecture.Conjecture 1 (see [1]).
IfG is a graph with order at least two, then tndi(G)≤Δ(G)+3.Conjecture1 has been confirmed for subcubic graphs, K4-minor free graphs, and planar graphs with large maximum degree [2–4].In 2015, Pilśniak and Woźniak [5] obtained tndi∑(G) for cycles, cubic graphs, bipartite graphs, and complete graphs. Moreover, they posed the following conjecture.Conjecture 2 (see [5]).
IfG is a graph with at least two vertices, then tndi∑(G)≤Δ(G)+3.Li et al. verified this conjecture forK4-minor free graphs [6] and planar graphs with the large maximum degree [7]. Wang et al. [8] confirmed this conjecture by using the famous Combinatorial Nullstellensatz that holds for any triangle free planar graph with maximum degree of at least 7. Several results about tndi∑(G) for planar graphs can be found in [9–11].In 2014, Dong and Wang [12] proved the following results.Theorem 3.
IfG is a graph with mad⁡(G)<3, then tndi∑(G)≤max⁡{Δ(G)+2,7}.Corollary 4.
IfG is a graph with mad⁡(G)<3 and Δ(G)≥5, then tndi∑(G)≤max⁡Δ(G)+2.Corollary 5.
LetG be a planar graph. If g(G)≥6 and Δ(G)≥5, then tndi∑(G)≤Δ(G)+2; and tndi∑(G)=Δ(G)+2 if and only if G has two adjacent vertices of maximum degree.The concept of list coloring was introduced by Vizing [13] and by Erdös et al. [14]. A k-assignment L of G is a list assignment L of integers to vertices and edges with L(v)=k for each vertex v and L(e)=k for each edge e. Atotal-L-coloring is a total coloring ϕ of G such that ϕ(v)∈L(v) whenever v∈V(G) and ϕ(e)∈L(e) whenever e∈E(G). We state that G has aneighbor sum distinguishing total-L-coloring if G has a total-L-coloring such that w(u)≠w(v) for all uv∈E(G). The smallest integer k such that G has a neighbor sum distinguishing total-L-coloring for every k-assignment L, denoted by Ch∑′′(G), is called theneighbor sum distinguishing total-choice number.Qu et al. [15] proved that Ch∑′′(G)≤Δ(G)+3 for any planar graph G with Δ(G)≥13. Yao et al. [16] studied Ch∑′′(G) of d-degenerate graphs. Later, Wang et al. [17] confirmed Conjecture 2 true for planar graphs without 4-cycles. For H⊆G, we let LH denote a list L restricted to any proper subgraph H of G. In this paper, we strengthen Theorem 3 by giving analogous results for Ch∑′′(G).


## 2. Main Results

The following lemma is obvious, so we omit the proof.Lemma 6.
LetS1=S2=⋯=Sk=k+1 and S∗={a1+a2+⋯+ak∣ai∈Si,ai≠aj,1≤i<j≤k}. Then S∗≥k+1.Proof.
We proceed by induction onk.
Ifk=1, then S1=2; then Lemma 6 holds. Assume that k>1. Suppose that Lemma 6 holds for k-1. Let a=min⁡(S1∪S2∪⋯∪Sk). Without loss of generality, let a∈S1. Let Ti⊆Si be such that Ti=k and a∉Ti for i=1,2,…,k. By induction hypothesis, we have T∗≥k. Thus {a+t2+t3+⋯+tk}⊆S∗, where ti∈Ti,tj∈Tj for 2≤i,j≤k and ti≠tj for i≠j. So S∗≥k. Let t2′+⋯+tk′=max⁡T∗ with ti′∈Ti,tj′∈Tj for 2≤i,j≤k and ti′≠tj′ for i≠j and b∈S1∖{a,t2′,t3′,…,tk′}. Thus b+t2′+t3′+…+tk′>max⁡{a+t2+t3+⋯+tk} and b+t2′+t3′+⋯+tk′∈S∗. Therefore, we obtain S∗≥k+1.Lemma 7 (see [12]).
LetS1,S2 be two sets and let S3={a+b∣a∈S1,b∈S2,a≠b}. If S1≥2 and S2≥3, then S3≥3.Theorem 8.
IfG is a graph with mad⁡(G)<3, then Ch∑′′(G)≤k, where k=max⁡{Δ(G)+2,7}.Proof. The proof is proceeded by contradiction. Assume that G is a minimum counterexample. Let Lv≥k for each vertex v and Le≥k for each edge e in G. For any proper subgraph G′ of G, we always assume that there is a neighbor sum distinguishing total-LG′-coloring ϕ of G′ by minimality of G. For convenience, we use a total-LG′-coloring ϕ of G′ to denote a neighbor sum distinguishing total-LG′-coloring ϕ of G′ and we use F(v)={ϕ(u),ϕ(uv)∣uv∈E(G′)} for v∈V(G) and F(uv)={ϕ(u),ϕ(v),ϕ(ur),ϕ(vs)∣ur∈E(G′),vs∈E(G′)} for uv∈E(G).LetH be the graph obtained by removing all leaves of G. Then H is a connected graph with mad(H)≤mad(G)<3. The properties of the graph H are collected in the following claims.Claim 1.
Each vertex inH has degree of at least 2.Proof.
Suppose to the contrary thatH contains a vertex v with dH(v)≤1. If dH(v)=0, then G is the star K1,Δ(G)-1 and Ch∑′′(G)=Δ(G); then we obtain a total-LG-coloring ϕ of G, a contradiction to the choice of G. Assume that dH(v)=1. Let u and vi be the neighbors of v where i=1,2,…,l=Δ(G)-1 and dG(vi)=1. Let G′=G-vv1. First, we uncolor vi where i=1,2,…,Δ(G)-1. Then we color vv1 with a color in L(vv1)∖(F(vv1)∪{w(u)-w(v)}). Next, we color vi with a color in L(vi)∖(F(vi)∪{(w(v)-w(vi)}) for i=1,2,…,Δ(G)-1; then we obtain a total-LG-coloring ϕ of G, a contradiction to the choice of G.Claim 2.
IfdH(u)=2, then dG(u)=2.Proof.
Suppose to the contrary thatdG(u)=k≥3. Let u1,u2 be the neighbors of u and vi be all neighbors of u which are leaves in G for i=1,2,…,l=dG(u)-2.
Case
1 (dG(u)=3). Let G′=G-v1 and L′(uv1)=L(uv1)∖(F(uv1)∪{w(u1)-w(u),w(u2)-w(u)}). We color uv1 with a color in L′(uv1) and color v1 with a color in L(v1)∖(F(v1)∪{w(u)-w(v1)}). Thus we obtain a total-LG-coloring ϕ of G, which is a contradiction to the choice of G.
Case
2 (dG(u)≥4). Let G′=G-{v1,…,vl}, where l=dG(u)-2. Let Ai=L(uvi)-{ϕ(u),ϕ(uu1),ϕ(uu2)}, where i=1,2,…,l. Then |Ai|≥Δ(G)-1≥l+1≥3, where i=1,2,…,l. By Lemma 6, we have at least l+1≥3 color sets available for the edge set {uvi|i=1,2,…,l} to guarantee w(u)=w(ui) for i=1,2. Since at most two color sets may cause w(u)=w(u1) or w(u)=w(u2), we have at least one color set available for the edge set {uvi∣i=1,2,…,l}. Finally, we color vi with the color in L(vi)∖(F(vi)∪{w(u)-w(vi)}) for i=1,2,…,l=dG(u)-2; then we obtain a total-LG-coloring ϕ of G, which is a contradiction to the choice of G.Claim 3.
A 2-vertexu is not adjacent to a 3-vertex.Proof.
Suppose to the contrary thatu is adjacent to a 3-vertex v in H. Let v1, v2 be the neighbors of v and s be the other neighbor of u.
Case
1 (dG(v)=3). Let G′=G-uv. First, we uncolor u. Next, we color uv with a color in L(uv)∖(F(uv)∪{w(v1)-w(v),w(v2)-w(v)}). Later, we color u with a color in L(u)∖(F(u)∪{w(v)-w(u),w(s)-w(u)}); then we obtain a total-LG-coloring ϕ of G, which is a contradiction to the choice of G.
Case
2 (dG(v)≥4). Let x1,x2,…,xt be the other neighbors of v such that dG(xi)=1 for all i=1,2,…,t=dG(u)-3. Let G′=G-{uv,vx1}. First, we uncolor all vertices u and xi, i=1,2,…,t. Consider L′(vx1)=L(vx1)∖F(vx1) and L′(uv)=L(uv)∖F(uv). We can see that L′vx1≥3 and L′uv≥2. By Lemma 7, we can choose ϕ(vx1)∈L′(vx1) and ϕ(uv)∈L′(uv) such that w(v)≠w(v1) and w(v)≠w(v2). Next, we color u with a color in L(u)∖(F(u)∪{w(v)-w(u),w(s)-w(u)}) and color xi with a color in L(xi)∖(F(xi)∪{w(v)-w(xi)}) for i=1,2,…,t; then we obtain a total-LG-coloring ϕ of G, which is a contradiction to the choice of G.Claim 4.
A 4-vertexu is adjacent to at most two 2-vertices.Proof.
Suppose to the contrary thatu is adjacent to three 2-vertices v1,v2,v3 and the other vertex v. Let vi′ be the neighbor of vi for i=1,2,3.
Case
1 (dG(u)=4). Let G′=G-uv1 and L′(uv1)=L(uv1)∖(F(uv1)∪{w(v)-w(u)}). First, we uncolor all vertices v1,v2,v3. Next, we color uv1 with a color in L′(uv1) and color vi with a color in L(vi)∖(F(vi)∪{w(u)-w(vi),w(vi′)-w(vi)}) for i=1,2,3. Thus we obtain a total-LG-coloring ϕ of G, which is a contradiction to the choice of G.
Case
2 (dG(u)≥5). Let x1,x2,…,xt be the neighbors of u such that dG(xi)=1 for all i=1,2,…,t=dG(u)-4. Let G′=G-ux1. First, we uncolor vertices vi and xj where 1≤i≤3, 1≤j≤t. Next, we choose ϕ(ux1)∈L(ux1)∖(F(ux1)∪{w(v)-w(u)}). After that, we color vi with a color in L(vi)∖(F(vi)∪{w(u)-w(vi),w(vi′)-w(vi)}) for i=1,2,3 and color xj with a color in L(xj)∖(F(xj)∪{w(u)-w(xj)}) for j=1,2,…,t. Thus we obtain a total-LG-coloring ϕ of G, which is a contradiction to the choice of G.Claim 5.
A 5-vertexu is adjacent to at most four 2-vertices.Proof.
Suppose to the contrary thatu is adjacent to five 2-vertices v1,v2,v3,v4,v5. Let x1,x2,…,xt be the other neighbors of u (if they exist) such that dG(xi)=1 for all i=1,2,…,t=dG(u)-5 and vi′ be the neighbor of vi for i=1,2,3,4,5. Let i=1,2,3,4,5 and j=1,2,…,t=dG(u)-5 and G′=G-uv1. First, we uncolor vertices vi and xj. Next, we color uv1 with a color in L(uv1)∖F(uv1). After that, we color vi with a color in L(vi)∖(F(vi)∪{w(u)-w(vi),w(vi′)-w(vi)}). Finally, we color xj with a color in L(xj)∖(F(xj)∪{w(u)-w(xj)}). Thus we obtain a total-LG-coloring ϕ of G, which is a contradiction to the choice of G.By Claim1, we have Δ(H)≥2.Suppose thatΔ(H)=2. By Claims 1 and 2, G is a cycle. One can obtain that Ch∑′′(G)≤7, a contradiction to the choice of G.Suppose thatΔ(H)=3. By Claim 3, H is a 3-regular graph. Thus we have mad(H)=3, which is a contradiction.Suppose thatΔ(H)≥4. We complete the proof by using the discharging method. Define an initial charge function ch(v)=dH(v) for every v∈V(H). Next, rearrange the weights according to the designed rule. When the discharging is finished, we have a new charge ch′(v). However, the sum of all charges is kept fixed. Finally, we want to show that ch′(v)≥3 for all v∈V(H). This leads to the following contradiction:(1)3=3VHVH≤∑v∈VHw′vVH=∑v∈VHwvVH=2EHVH≤madH<3.Letv∈V(H). Assume that dH(v)=2 and uv∈E(H). Then vertex u gives charge 1/2 to v.Consider a vertexv∈V(H). By Claim 1, we have dH(v)≥2.IfdH(v)=2, then v is adjacent to at least two 4-vertices by Claim 3. Hence ch′(v)≥ch(v)+(2×(1/2))=3.IfdH(v)=3, then ch′(v)=ch(v)=3.IfdH(v)=4, then v is adjacent to at most two 2-vertices by Claim 4. Hence ch′(v)≥ch(v)-(2×(1/2))=3.IfdH(v)=5, then v is adjacent to at most four 2-vertices by Claim 5. Hence ch′(v)≥ch(v)-(4×(1/2))=3.IfdH(v)≥6, then ch′(v)≥ch(v)-((1/2)dH(v))=(1/2)dH(v)≥3.From the above discussion, we have∑v∈V(H)ch′(v)≥3, which is a contradiction. This completes the proof of Theorem 8.



---

*Source: 5897049-2017-11-07.xml*