# Strong List Edge Coloring of Subcubic Graphs

Authors: Hongping Ma; Zhengke Miao; Hong Zhu; Jianhua Zhang; Rong Luo
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We study strong list edge coloring of subcubic graphs, and we prove that every subcubic graph with maximum average degree less than 15/7, 27/11, 13/5, and 36/13 can be strongly list edge colored with six, seven, eight, and nine colors, respectively.


---

## Body

## 1. Introduction

All graphs in this paper are finite and simple. For a graphG with vertex set V(G) and edge set E(G), a proper edge coloring of G is an assignment of colors to the edges of G so that no two adjacent edges receive the same color. A strong edge coloring is a proper edge coloring so that two edges adjacent to a common edge receive different colors. The strong chromatic index of G, denoted by χs′(G), is the minimum number of colors needed for a strong edge coloring of G.Strong edge coloring was introduced by Fouquet and Jolivet [1, 2]. This type of coloring can be used to represent the conflict-free channel assignment in radio networks.Denote byΔ the maximum degree of the graph. In 1985, Erdös and Nes˘etr˘il conjectured that the strong chromatic index of a graph is at most (5/4)Δ2 when Δ is even and (1/4)(5Δ2-2Δ+1) when Δ is odd. Andersen proved the conjecture for Δ=3 [3]. Strong edge coloring of cubic Halin graphs has been studied in [4, 5].Letmad(G)=maxH⊆G,|V(H)|≥1(2|E(H)|/|V(H)|) be the maximum average degree of the graph G. Hocquard and Valicov [6] considered the subcubic graphs with bounded maximum average degree, and they proved the following results.Theorem 1.
LetG be a subcubic graph.(i)
Ifmad(G)<15/7, then χs′(G)≤6.(ii)
Ifmad(G)<27/11, then χs′(G)≤7.(iii)
Ifmad(G)<13/5, then χs′(G)≤8.(iv)
Ifmad(G)<36/13, then χs′(G)≤9.The main purpose of this paper is to generalize the study of list version so that the admissible colors on edges are constrained. An edge listL of a graph G is a mapping that assigns a finite set to each edge of G. Denote L={L(e):e∈E(G)}. We say that L is a k-edge list if |L(e)|≥k for each edge e in G. The graph G is strongly L-edge colorable if there exists a strong edge coloring c of G such that c(e)∈L(e) for every edge e of G. For a positive integer k, a graph G is strongly k-edge choosable if for every k-edge list L, G is strongly L-edge colorable. The strong list chromatic index χls′(G) is the minimum positive integer k for which G is strongly k-edge choosable.In this paper, we consider strong list edge coloring of subcubic graphs and extend Theorem1 to the list version. We prove the following theorem.Theorem 2.
LetG be a subcubic graph.(i)
Ifmad(G)<15/7, then χls′(G)≤6.(ii)
Ifmad(G)<27/11, then χls′(G)≤7.(iii)
Ifmad(G)<13/5, then χls′(G)≤8.(iv)
Ifmad(G)<36/13, then χls′(G)≤9.The paper is organized as follows. In Section2, we will prove two lemmas which will be applied a lot in the proof of Theorem 2. Theorem 2 will be proved in Sections 3, 4, 5, and 6.Before proceeding we introduce some notations and definitions. The degree of a vertexv in a graph is denoted by d(v). A vertex of degree k is called a k-vertex. A k-neighbor of v is a k-vertex adjacent to v. N(v) is the set of the neighbors of v. A t-thread of G is a path Pt=x1x2⋯xt with d(xi)=2 for i=1,2,…,t. Two edges are at distance at most 2 if either they are adjacent or they are adjacent to a common edge. Denote by N2(e) the set of edges at distance at most 2 from the edge e. Define LSC(N2(e)) as the set of colors used by edges in N2(e). Denote L′(e)=L(e)∖LSC(N2(e)).


## 2. Lemmas

Lemma 3.
LetG be the graph obtained from a path x1x2x3x4x5 by adding two vertices u, v so that u is adjacent to x3 and v is adjacent to x4. Let L be an edge list of G. If |L(xixi+1)|≥3 for i=1,2,3, |L(x4x5)|≥2, |L(x3u)|≥5, and |L(x4v)|≥4, then G has a strong L-edge coloring.Proof.
If there is a colora∈L(x1x2)∩L(x4x5), then we first color the edges x1x2 and x4x5 with the color a. So we can further color the rest of edges with the available colors in the order of x2x3, x3x4, x4v, and x3u.
Now we assume thatL(x1x2)∩L(x4x5)=∅. Denote L(x1x2)={a,b,c} and L(x4x5)={d,e}. If there is a color t∈L(x2x3)∖{a,b,c}, we first color the edge x2x3 with the color t. Then after coloring all the other edges, the edge x1x2 still has one color available. Therefore, we can color the edges with an available color in the order of x4x5, x3x4, x4v, and x3u. Thus we can further assume L(x2x3)={a,b,c}. Similarly, we can also assume that L(x3x4)={a,b,c}. If there is a color s∈{a,b,c}∩L(x4v), then we first color the edges x1x2 and x4v with the color s. So we can further color the rest of edges with the available colors in the order of x2x3, x3x4, x3u, and x4x5. Therefore we can assume that {a,b,c}∩L(x4v)=∅. We first color the edges x1x2,x2x3,x3x4, and x4x5 with the colors a, b, c, and d, respectively. Then |L′(x3u)|≥1, |L′(x4v)|≥3, and thus we can further color the edges x3u and x4v. This completes the proof of the lemma.Lemma 4.
LetP=xyzuv be a path and L an edge list so that |L(e)|≥2 if e∈{xy,zu,uv} and |L(yz)|≥3. Then P has a strong L-edge coloring.Proof.
We only need to prove the lemma when each|L(e)| is equal to its lower bound. If there is a color a∈L(xy)∩L(uv), we color both xy and uv with a. Then |L′(zu)|≥1 and |L′(yz)|≥2, so we can further color the edges zu and yz.
Now assume thatL(xy)∩L(uv)=∅. Denote L(xy)={a,b} and L(uv)={c,d}. If a∈L(zu), we first color zu with a and the edge xy with b and then color the edge yz with an available color. Since a,b∉L(uv), there is still one color available for the edge uv. Thus P has a strong L-edge coloring. Similarly we can obtain a strong L-edge coloring of P if L(zu)∩L(uv)≠∅. Now we further assume L(zu)∩[L(xy)∪L(uv)]=∅. That is, L(xy), L(zu), and L(uv) are mutually disjoint, and it is easy to see that P has a strong L-edge coloring.


## 3. Proof of (i) of Theorem2

LetH be a counterexample with |E(H)| as small as possible. Then there exists a 6-edge list L such that H is not strongly L-edge colorable. We can assume that H is connected; otherwise, we can color independently each connected component. A 3-vertex is bad if it is adjacent to a 1-vertex; otherwise it is good.Claim 1.
A 1-vertex is adjacent to a 3-vertex inH and each bad 3-vertex is adjacent to two 3-vertices.Proof.
Letu be a 1-vertex and v its neighbor. Since H is a minimum counterexample, H∖{uv} has a strong L-edge coloring. If d(v)=2 or v is adjacent to only one 3-vertex, we have |L′(uv)|≥1, and thus we can easily extend the coloring to H, a contradiction.Claim 2.
H does not contain a t-thread with t≥3.Proof.
Suppose thatH contains a t-thread x1x2⋯xt with t≥3. Then H′=H∖{x1x2,x2x3} has a strong L-edge coloring by the minimality of H. It is easy to see that |L′(x1x2)|≥2 and |L′(x2x3)|≥2. Hence we can extend the coloring of H′ to H, a contradiction.Claim 3.
H does not contain a path x2x3x4x5 such that x2,x3,x4,x5 are all bad 3-vertices.Proof.
Suppose thatH contains such a path x2x3x4x5. Let x1,u,v be the 1-neighbors of x2,x3,x4, respectively. By the minimality of H, H∖[{xixi+1∣i=1,…,4}∪{x3u,x4v}] has a strong L-edge coloring f. Since |L(e)|≥6, we have |L′(xixi+1)|≥3 for each i=1,2,3, |L′(x4x5)|≥2, |L′(x3u)|≥5, and |L′(x4v)|≥4. By Lemma 3, we can further extend the coloring to the rest of the edges of H to obtain a strong L-edge coloring of H, a contradiction.Claim 4.
H does not contain the following three configurations:(1)
a pathxuvwyrstt2 such that u, v, w, r, s, and t are bad 3-vertices, y is a good vertex, and another neighbor z of y is a 2-vertex (see Figure 1),(2)
a pathxuvwyrstt2 such that u, v, w, r, s, and t are bad 3-vertices, y is a good vertex, and another neighbor z of y is a bad 3-vertex (see Figure 2),(3)
a pathxuvwyrs such that u, v, w, r, and s are bad 3-vertices, y is a good vertex, and another neighbor z of y is a bad 3-vertex which is also adjacent to a bad 3-vertex (see Figure 3).Figure 1
The configuration of Claim4(1).Figure 2
The configuration of Claim4(2).Figure 3
The configuration of Claim4(3).Proof.
(1) Suppose that there exists a pathxuvwyrstt2 such that u, v, w, r, s, and t are bad 3-vertices, y is a good vertex, and y is adjacent to a 2-vertex (see Figure 1). Denote N(u)={x,u1,v}, N(v)={u,v1,w}, N(w)={v,w1,y}, N(r)={y,r1,s}, N(s)={r,s1,t}, and N(t)={s,t1,t2}, where u1, v1, w1, r1, s1, t1 are 1-vertices, and N(x)={u,x1,x2}, N(y)={w,r,z}, N(z)={y,z1}, and N(t2)={t,t3,t4}. Then H∖{uu1,uv,vv1,vw,ww1,wy,yz,yr,rr1,rs,ss1,st,tt1} has a strong L-edge coloring C by the minimality of H. We are going to extend the coloring C to H. For each uncolored edge e in H, we use L′(e) to denote the set of colors available for e. Then L′(uu1)=L(uu1)∖{C(xu),C(xx1),C(xx2)} has at least three colors because |L(e)|≥6 for each edge e in H. Similarly we have the following:(1)
|L′(e)|≥3 if e∈{uu1,uv,st,tt1,yz},(2)
|L′(e)|≥5 if e∈{vv1,vw,wy,yr,rs,ss1},(3)
|L′(e)≥6 if e∈{ww1,rr1}.
By Lemma3, we only need to(i)
either extend the coloringC to yz,yr,rs,ss1,st,tt1 so that there are still two colors available for rr1,(ii)
or extend the coloringC to yz,yr,rr1,rs,ss1,st,tt1 so that |{C(yz),C(yr),C(rr1),C(rs)}∩[L(wy)∖{C(zz1)}]|≤3.
If there is a colora∈L′(yz)∩L′(st), we color the edges yz and st with the color a. Then we may further color the edges tt1, ss1, rs, and yr. This gives a coloring in (i). Thus L′(yz)∩L′(st)=∅. Similarly we can show L′(yz)∩L′(ss1)=∅. Denote L′(yz)={a,b,c}.
Ifa∉L′(yw), we first color the edge yz with the color a, and then by Lemma 3, we can further extend C to the edges yz, yr, rr1, rs, ss1, st, and tt1. Since the edge yz is colored with a not in L′(wy), such extension satisfies (ii). Therefore L′(yz)⊆L′(wy). Similarly we can show that L′(wy)=L′(yr)=L′(rs). Denote L′(wy)={a,b,c,d,e}. We first color the edges yz, yr, and rs with a, b, and c, respectively. Then L′(wy)∖{a,b,c} has two colors. By Lemma 3, we can first extend C to the edges uu1, uv, vv1, vw, ww1, and wy. Since {a,b,c}∩[L′(st)∪L′(ss1)]=∅, we can further color the edges tt1, st, rr1, and ss1 in order.
In each case, we can extend the coloringC to a strong L-edge coloring of H, a contradiction. Therefore, the configuration in Figure 1 does not exist.
Similarly we can also show that the configurations in Figures2 and 3 do not exist either.LetM(x)=d(x)-(15/7) be the initial charge of x for each vertex x. Then ∑x∈V(H)‍M(x)<0. We assign a new charge to each vertex according to the following rules.R1. For each good 3-vertexx, if xx1x2⋯xtxt+1 is a path in which x1x2⋯xt is a maximal t-thread, then x sends 1/14 to each xi for i=1,…,t, and if xx1x2⋯xtxt+1 is a path in which xi is a bad 3-vertex for each i=1,…,t, x sends 1/7 to each xi for i=1,…,t.R2. Each bad 3-vertex sends8/7 to its 1-neighbor.Now we consider the new chargeM′(x) for each vertex x.(1)
Ifd(x)=1, then by Claim 1, x is adjacent to a bad 3-vertex. Thus M′(x)=1-(15/7)+(8/7)=0.(2)
Ifd(x)=2, then by R1, x receives 2×(1/14)=(1/7) in total from some 3-vertices. Thus M′(x)=2-(15/7)+(1/7)=0.(3)
Ifx is a bad 3-vertex, then M′(x)=(8/7)-(8/7)=0.(4)
Assume thatx is a good 3-vertex. Denote by t and s the numbers of bad 3-vertices and 2-vertices receiving charges from x, respectively. By Claim 2 and Claim 4, we have 0≤t≤6 and 0≤s≤6. Hence M′(x)=3-(15/7)-(t/7)-(s/14)=(6/7)-(t/7)-(s/14).Ift=0, then s≤6. Hence M′(x)≥(6/7)-(6/14)>0.If0<t≤3, then s≤4. Hence M′(x)≥(6/7)-(3/7)-(4/14)>0.Ift=4, then s≤2. Hence M′(x)≥(6/7)-(4/7)-(2/14)>0.Ift=5, then s≤2. Hence M′(x)≥(6/7)-(5/7)-(2/14)≥0.Ift=6, then s=0. Hence M′(x)≥(6/7)-(6/7)≥0.Therefore we have0≤∑x∈V(H)‍M′(x)=∑x∈V(H)‍M(x)<0.


## 4. Proof of (ii) of Theorem2

LetH be a counterexample with |E(H)| as small as possible. Then there exists a 7-edge list L such that H is not strongly L-edge colorable.Claim 5.
There is no 1-vertex inH.Proof.
Suppose to the contrary thatH contains a 1-vertex u, such that v is its neighbor. Since H is a minimum counterexample, H′=H∖{uv} has a strong L-edge coloring. Hence |L′(uv)|≥1, we can easily extend this coloring to H, a contradiction.Claim 6.
H does not contain a t-thread with t≥3.Proof.
The proof is similar to that of Claim2 and thus omitted.Claim 7.
H does not contain the following two configurations:(1)
A pathxuvw such that u and v are 2-vertices, x is a 3-vertex, and w is a 3-vertex which has two 2-neighbors and one 3-neighbor (see Figure 4).(2)
A pathuwv where d(u)=d(v)=3 and d(w)=2 and both u and v have three 2-neighbors (see Figure 5).Figure 4
The configuration of Claim7(1).Figure 5
The configuration of Claim7(2).Proof.
(
1
) Suppose that H contains a path xuvw in Figure 4. Let H′=H∖{uv,vw,wy}. Since H is a minimal counterexample, H′ has a strong L-edge coloring. Then |L′(wy)|≥1, |L′(vw)|≥2, and |L′(uv)|≥3, and we can extend the coloring to H, a contradiction.
(
2
) Suppose that H contains the configuration in Figure 5, where y, u1, w, v1, and z are 2-vertices and u and v are 3-vertices. Since H is a minimum counterexample, H′=H∖{yu,uu1,uw,wv,vv1,vz} has a strong L-edge coloring. Now |L′(uu1)|≥3 and |L′(vv1)|≥3. We first color the two edges uu1 and vv1 to obtain a strong L-edge coloring of H∖{yu,uw,wv,vz}. It is easy to check that |L′(yu)|≥2, |L′(uw)|≥3, |L′(wv)|≥3, and |L′(vz)|≥2. By Lemma 4, we can further extend the coloring to H, a contradiction.LetM(x)=d(x)-(27/11) be the initial charge of x for each vertex x. Then ∑x∈V(H)‍M(x)<0. A 2k-vertex is a 2-vertex with k 3-neighbors. We assign a new charge to each vertex according to the following rules.R1. Letx be a 22-vertex and u a 3-neighbor of x. If u is adjacent to three 2-vertices, then u sends 2/11 to x; otherwise u sends 3/11 to x.R2. Letx be a 21-vertex and u be its 3-neighbor. u sends 5/11 to x.(1)
Ifx is a 21-vertex, then by R2, x receives 5/11 from its 3-neighbor. Thus M′(x)=2-(27/11)+(5/11)=0.(2)
Ifx is a 22-vertex with two neighbors u and v and if one of u,v has three 2-neighbors, then by Claim 7 the other one has at most two 2-neighbors. Hence x receives (2/11)+(3/11)=5/11 from its neighbors. If neither u nor v has three 2-neighbors, then x receives (3/11)+(3/11)=6/11 from its neighbors. Therefore M′(x)≥2-(27/11)+(5/11)≥0.(3)
Assumed(x)=3. By Claim 7, we only consider the following three cases: (a) if x is adjacent to three 22-vertices, then x sends out 3×(2/11)=6/11 to its neighbors; (b) if x is adjacent to at most two 22-vertices, then it sends out at most 2×(3/11)=6/11 to its neighbors; (c) if x is adjacent to one 21-vertex, then it sends out 5/11 to its neighbors. In each case, we have M′(x)≥3-(27/11)-(6/11)=0.Therefore we have0≤∑x∈V(H)‍M′(x)=∑x∈V(H)‍M(x)<0.


## 5. Proof of (iii) of Theorem2

LetH be a counterexample with |E(H)| as small as possible. Then there exists an 8-edge list L such that H is not strongly L-edge colorable.Claim 8.
There is no 1-vertex inH.Proof.
The proof is similar to that of Claim5 and thus omitted.Claim 9.
There are no two adjacent 2-vertices inH.Proof.
Suppose that there are two adjacent 2-verticesu and v. Let w be the other neighbor of v. Since H is a minimum counterexample, H∖{uv,vw} has a strong L-edge coloring. Then |L′(uv)|≥3 and |L′(vw)|≥1. Hence, we can extend the coloring to H easily, a contradiction.Claim 10.
A 3-vertex is not adjacent to three 2-vertices inH.Proof.
Suppose to the contrary that a 3-vertexu is adjacent to three 2-vertices x, v, and w. Since H is a minimum counterexample, H∖{xu,uv,uw} has a strong L-edge coloring. Thus |L′(xu)|≥3, |L′(uv)|≥3, and |L′(uw)|≥3. Therefore, we can extend the coloring to H, a contradiction.Claim 11.
H does not contain a path P=uvwxy where u, w, and y are 2-vertices and v and x are 3-vertices.Proof.
Suppose to the contrary thatH contains a path uvwxy, where u, w, and y are 2-vertices and v and x are 3-vertices. By the minimality of H, H∖{vw,wx} has a strong L-edge coloring. Uncolor uv and xy. It is easy to check that |L′(uv)|≥2, |L′(xy)|≥2, |L′(vw)|≥3, and |L′(wx)|≥3. By Lemma 4, we can extend the coloring to the path uvwxy to obtain a strong L-edge coloring of H, a contradiction.LetM(x)=d(x)-(13/5) be the initial charge of x for each vertex x. Then ∑x∈V(H)‍M(x)<0. We assign a new charge to each vertex according to the following rule.R. Letx be a 3-vertex and t the number of 2-neighbors of x. x sends 2/5t to each adjacent 2-vertices if t≠0.ObviouslyM′(x)≥0 if d(x)=3.Letx be a 2-vertex and u,v its neighbors. By Claims 9 and 10, both u and v are 3-vertices and have at most two 2-neighbors. If one 3-neighbor of x is adjacent to two 2-vertices, then by Claim 11, the other neighbor of x is adjacent to only one 2-vertex. Hence x receives (1/5)+(2/5)=3/5 from its neighbors. If each neighbor of x is adjacent to only one 2-vertex, then x receives (2/5)+(2/5)=4/5 from its neighbors. Hence M′(x)≥2-(13/5)+(3/5)=0.Therefore we have0≤∑x∈V(H)‍M′(x)=∑x∈V(H)‍M(x)<0. This contradiction completes the proof.


## 6. Proof of (iv) of Theorem2

LetH be a counterexample with |E(H)| as small as possible. Then there exists a 9-edge list L such that H is not strongly L-edge colorable.Claim 12.
There is no 1-vertex inH.Proof.
The proof is similar to that of Claim5 and thus omitted.Claim 13.
There are no two adjacent 2-vertices inH.Proof.
The proof is similar to that of Claim9 and thus omitted.Claim 14.
No 3-vertex is adjacent to two 2-vertices inH.Proof.
Suppose to the contrary that a 3-vertexu is adjacent to two 2-vertices v, w. Let x be the third neighbor of u. Since H is a minimum counterexample, H∖{uv,uw,ux} has a strong L-edge coloring. Then |L′(ux)|≥1, |L′(uv)|≥3, and |L′(uw)|≥3. Hence we can extend the coloring to H, a contradiction.Claim 15.
If a 3-vertexx has a 2-neighbor, then each 3-neighbor of x is not adjacent to a 2-vertex.Proof.
Suppose to the contrary thatx has a 3-neighbor y such that y is also adjacent to a 2-vertex u. Let z be the 2-neighbor of x. We first assume that u=z. By the choice of H, H∖{xz,yz} has a strong L-edge coloring with the edges xz and yz uncolored. Then it is easy to see that |L′(xz)|≥3 and |L′(yz)|≥3, and thus we may further color the edges xz and yz to get a strong L-edge coloring of H, a contradiction.
Now we assume thatu≠z. Let v be the other neighbor of z. Let C be a strong L-edge coloring of H∖{vz,zx,xy,yu} obtained from a strong L-edge coloring of H-{z} by uncoloring the edges xy and yu. It is easy to see that |L′(vz)|≥2, |L′(zx)|≥3, |L′(xy)|≥2, and |L′(yu)|≥2. By Lemma 4, C can be extended to those four uncolored edges, and thus H has a strong L-edge coloring, a contradiction.LetM(x)=d(x)-(36/13) be the initial charge of x for each vertex x. Then ∑x∈V(H)‍M(x)<0. We assign a new charge to each vertex according to the following rules.R1. Each2-vertex receives 5/13 from each adjacent vertex.R2. If a 3-vertexx is adjacent to a 2-vertex then x receives 1/13 from each 3-neighbor.Obviously ifd(x)=2, then M′(x)=2-(36/13)+(10/13)=0.Ifd(x)=3 and x is not adjacent to a 2-vertex, then M′(x)≥3-(36/13)-3×(1/13)=0.Ifd(x)=3 and x is adjacent to a 2-vertex, then by Claims 14 and 15, M′(x)=3-(36/13)-(5/13)+2×(1/13)=0.Therefore we have0≤∑x∈V(H)‍M′(x)=∑x∈V(H)‍M(x)<0. This contradiction completes the proof.


## 7. Conclusion

This paper studies strong list edge coloring of subcubic graphs. The result can be used to deal with the conflict-free channel assignment problem in wireless radio networks when the admissible channels on the links between transceivers are constrained. We believe that the upper bounds on the maximum average degree in Theorem2 are not sharp. It would be interesting to find sharp upper bounds for the maximum average degree.



---

*Source: 316501-2013-04-29.xml*