# List Edge Colorings of Planar Graphs without Adjacent 7-Cycles

Authors: Wenwen Zhang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we get thatG is edge-k-choosable (k=max10,ΔG) for planar graph G without adjacent 7-cycles.


---

## Body

## 1. Introduction

Edge coloring and list edge coloring of graphs are very old fashioned problems in graph theory, and the research on such problems has a long history. DenoteZ+ as the set of the integers. Now, we only consider the list edge coloring problem of finite simple undirected graphs. Before describing the concept of list edge coloring in detail, we have to revisit fundamental conception of normal edge coloring. A graph G is k-edge-colorable if all edges of G can be colored by k colors such that no two adjacent edges get the same colors. Denoted χ′G as the edge chromatic number of a graph G, which is the smallest k∈Z+ satisfying G is k-edge-colorable. For each edge e of graph G, if we can assign a list Le of colors to it, then L is an edge assignment. Graph G is edge-L-colorable if G has a proper edge-coloring ϕ such that ϕe∈Le for each edge e of G, and ϕ is an edge-L-coloring. Graph G is edge-k-choosable if for every L satisfying Le≥kk∈Z+ for each edge e. Denote χl′G as the list-edge chromatic number of G which is the smallest k in Z+ such that G is edge-k-choosable.We will study the list edge colorings of planar graphs. Planar graph is a kind of graph broadly studied in graph coloring theory. The so-called plane graph is actually a special drawing method of planar graph, which can be embedded in the plane satisfying no two edges intersect geometrically except at a vertex to which they are both incident. Let us introduce some definitions and symbols needed. Given a plane graphG, we use VG,EG,FG,ΔG, and δG to indicate its vertex set, edge set, face set, maximum degree, and minimum degree, respectively. For a vertex v∈VG, let EGv or Ev be the set of edges which are incident with v. We use dGv or dv to indicate the degree of v in G, which is the number of edges in Ev. We use NGv or Nv to indicate the set of the vertices which are adjacent to v in G. Denoted k-vertex, k−-vertex, or k+-vertex as a vertex of degree k, at most k or at least k, respectively. A k (or k+)-neighbor of x is a k (or k+)-vertex which is adjacent to a vertex x. A k-cycle is a cycle of length k. Two cycles are adjacent, that is, the two cycles share at least a common edge. A 2-alternating cycle is an even cycle in which the 2-vertices appear alternately. For f∈FG, we use dGf to indicate the degree of a face, which is the number of edges incident with f where each cut edge is counted twice. Denote k-, k+-face as a face of degree k, at least k. For a k-face of G, we called it i1,i2,…,ik-face if the vertices incident with it are of degrees i1,i2,…,ik, respectively. We use fkv to indicate the number of k-faces which are incident with v, dkf the number of k-vertices which are incident with f, and dkv the number of k-vertices which are incident with v.List edge coloring was firstly put forward by Vizing [1] and later by Bollobas and Harris [2]. They posed Conjecture 1 which is later called the List Coloring Conjecture.Conjecture 1.
For every multigraphG, χl′G=χ′G.
So far, Conjecture1 has only been proved to be true for a few graphs, including bipartite multigraphs [3], complete graphs of odd order [4], multicircuits [5], graphs embedded in a surface of nonnegative characteristic and ΔG≥12 [6], and outer planar graphs [7]. For planar graphs, the readers can see [8–12].
Wang and Wu [13] proved that G is edge-k-choosable k=max10,ΔG for a planar graph G without 6-cycles with three chords. Now, we will study the planar graphs without adjacent 7-cycles and obtain:Theorem 1.
Suppose thatGis a planar graph which contains no adjacent 7-cycles. Then, Gis edge-k-choosable, wherek=max10,ΔG.From Theorem1, we can obtain the following corollary.Corollary 1.
Suppose thatGis a planar graph which contains no adjacent 7-cycles, andχl′G=ΔGforΔG≥10.


## 2. The Proofs of Theorem

Proof.
LetG=VG,EG,FG be a minimal graph satisfying the number of EG as little as possible; then, the graph G has the following properties.Lemma 1.
(see [14]). Let Gbe a planar graph, by the minimality hypothesis of graphG, and we have(1)
δG≥2andGis a connected graph(2)
Gdoes not contain edgev1v2satisfyingmindv1,dv2≤k/2anddv1+dv2≤k+1(3)
Gdoes not contain 2-alternating cycle
DenoteG2 as the induced subgraph of G by all 2-vertices of G, where EG2=v1v2|dv1=2. By Lemma 1(2) and (3), G2 contains no odd cycle and even cycle. Therefore, G2 must be a forest. Thereby, there must be a matching M in G2 and all 2-vertices in M are saturated. If v1v2∈M and dG2v1=2, then v2 is named the 2-master of v1 and v1 is the dependent of v2. Obviously, each 2-vertex has a 2-master and each k-vertex may be the 2-master of no more than one 2-vertex.Lemma 2.
(see [15]). Given X=x∈VG|dGx≤3 and Y=∪x∈XNx. Then, there is a bipartite subgraph M′ of G with partite sets X and Y satisfying dM′x=1, for any x∈X, and dM′y≤2, for any y∈Y.
Note that, in Lemma2, we mark y as the 3-master of x if xy∈M′ and x∈X.Lemma 3.
Suppose thatG is a planar graph which contains no adjacent 7-cycles and dv=9. Then,(1)
Iff3v=6 and one of its edges is not incident with any 3-face (as in Figure 1,1−10,1−11,1−13), then f7+v≥1(2)
Iff3v=7, then f7+v=2Figure 1
Vertexv is a 9-vertex, the various cases of f3v≥5.Proof.
LetNGv=v1,v2,…,v9, where all the neighbors vi1≤i≤9 of v are in an anticlockwise order. We use fi to indicate the face which is incident with v, vi, and vi+1i1≤i≤9.(1)
Now, we prove (1–10) in Figure1. Suppose that f1,f2,…,f5 and f7 are 3-faces. If f6 is a 4-face or 5-face or 6-face, then there will be adjacent 7-cycles in G. It must be df6≥7 and f7+v≥1. The proof process of (1–11) and (1–13) is similar, so we will not repeat it.(2)
Its proof process is similar to (1), so we will not repeat it.
Similarly, we can get the following two lemmas.Lemma 4.
Suppose thatG is a planar graph which contains no adjacent 7-cycles and dv=10. Then,(1)
Iff3v=5 and four of its edges are not on any 3-face (as shown in Figure 22−1), then f7+v≥1(2)
Iff3v=6 (as shown in figure 2−16−2−27), then f7+v≥1(3)
Iff3v=7 (as shown in figure 2−28−2−33), then f7+v≥2(4)
Iff3v=8 (as shown in figure 2−34,2−35), then f7+v=2Figure 2
Vertexv is a 10-vertex, the various cases of f3v≥5.Lemma 5.
Suppose thatG is a planar graph which contains no adjacent 7-cycles and dv=11. Then,(1)
Iff3v=8 and one of its edges is not on any 3-face (as shown in Figure 33−41,3−43), then f7+v≥1(2)
Iff3v=9 (as in figure 3−47), then f7+v=2
Now, we complete the proof by Euler’s formula. In [6], the authors proved χl′G=ΔG for every planar graph with ΔG≥12, so we only assume that ΔG≤11 in our proof. Suppose that G is already embedded in the plane. We can obtain(1)∑x∈VGdx−4+∑x∈FGdx−4=−8<0,by practical Euler’s formula VG−EG+FG=2.
Firstly, denotech as the original charge. For each x∈V∪F, let chx=dx−4. Therefore, ∑x∈V∪Fchx<0. Secondly, we formulate some rules to redistribute the original charge and each x∈V∪F will get a new charge ch′x. Note that the rules we formulated only move between the vertices and faces of the graph and have no effect on the total charge. Thirdly, we will show that ch′x≥0 (x∈V∪F). If we can do, then we will obtain an apparent contradiction 0≤∑ch′x=∑chx<0 (x∈V∪F). The proof of Theorem 1 is completed.
The discharging rules are formulated as in R1–R5. We usecx⟶y to indicate the charge from x to y:R1. Let dv=2, v1 be a 3-master vertex and v2 be 2-master vertex of v. Firstly, cv1⟶v=1. Secondly, if v is on a face f with df≥5, then cf⟶v=1/2 and cv2⟶v=1/2, otherwise cv2⟶v=1.R2. Let dv=3 and v1 and v2 be two 3-masters of v, then cv1⟶v=1 and cv2⟶v=1.R3. Every 5-vertex receives 2/15 from each of its 7+-neighbors.R4. Let f be a 3-face v1v2v3 with dv1≤dv2≤dv3.R4.1 If dv1=3 or 4, then cv2⟶f=1/2 and cv3⟶f=1/2.R4.2 If dv1≥5, then cvi⟶f=1/3 for i=1,2,3.R5. Let df≥5 and t=d2f. Each of 2-vertices on f receives 1/2 from f and other vertices remaining on f receives df−4−t⋅1/2/df−t from f.
Now, let us start to test and verifych′ is greater than or equal to 0 for all vertices and faces. It is easy to verify faces, so let us verify the new charge of every face firstly. Obviously, df≥3. If df=3, then ch′f=−1+min2×1/2,3×1/3=0 by R4; if df=4, then ch′f=chf=0; otherwise df≥5, by R5 ch′f≥1−t×1/2−df−4−t×1/2/df−t×df−t=0.
Let us verify the new charge for every vertex. Ifdv=i for 2≤i≤4, then ch′v=−2+1+min2×1/2,1=0 by R1, ch′v=−1+1=0 by R2, and ch′v=0, respectively. If dv=5, then v must be adjacent to 7+-vertices by Lemma 1(2). So, by R3 and R4, ch′v≥1+5×2/15−5×1/3=0. If dv=6, then v must be adjacent to 6+-vertices by Lemma 1(2). So, by R4 ch′v≥2−6×1/3=0. If dv=7, then f3v≤5, and by Lemma 1(2), v must be adjacent to 5+-vertices. So, by R3 and R4, ch′v≥7−4−5×1/3−7×2/15=8/15>0.
Suppose thatv be a 8-vertex. Then, f3v≤6 and v must be adjacent to 4+-vertices by Lemma 1(2). If f3v≤5, then by R3-R4 ch′v≥8−4−5×1/2−8×2/15=13/30>0. Otherwise, f3v=6. Since all the neighbors of 5-vertex must be 6+-vertices by Lemma 1(2), so every 3-face which is incident with 8-vertex has no more than a 5-vertex, that is, d5v≤6. So, by R3-R4, ch′v≥8−4−6×1/2−6×2/15=1/5>0.
Suppose thatv be a 9-vertex. Then, f3v≤7 and v must be adjacent to 3+-vertices by Lemma 1(2), and it may be the 3-master of no more than two 3-vertices. In the following, we will test it from three cases. Firstly, it is not the 3-master of any 3-vertex, and then, ch′v≥9−4−7×1/2−9×2/15=3/10>0 by R3 and R4.
Secondly,v is the 3-master of only one 3-vertex. If f3v≤5, then ch′v≥9−4−1−5×1/2−8×2/15=13/30>0 by R3, R4, and R5. Suppose f3v=6 (as shown in Figure 1, (1–10)–(1–15)). Since all the neighbors of 5-vertex should be 6+-vertices by Lemma 1(2), so every 3-face incident with 9-vertex has no more than one 5-vertex, that is, d5v≤6. So, ch′v≥9−4−1−6×1/2−6×2/15=1/5>0 by R3–R5. Suppose f3v=7 (as shown in figure, (1–16)–(1–17)). If v has a 5-neighbor u, then the 3-face which is incident with u and v must be a 5,6+,9-face and by R4 this 3-face receives 1/3 from v. So, ch′v≥9−4−1−max7×1/2,6×1/2+1/3+2/15,5×1/2+2×1/3+2×2/15,4×1/2+3×1/3+3×2/15,3×1/2+4×1/3+4×2/15,2×1/2+5×1/3+5×2/15,1/2+6×1/3+6×2/15=1/2>0 by R3, R4, and R5.Thirdly,v is the 3-master of two 3-vertices. If f3v≤4, then ch′v≥9−4−2−4×1/2−7×2/15=1/15>0 by R3, R4, and R5. Suppose f3v=5 (as shown in Figure 1, (1-1)–(1–9)). Then, ch′v≥9−4−2−max5×1/2+3×2/15,4×1/2+1/3+4×2/15,3×1/2+2×1/3+5×2/15,2×1/2+3×1/3+6×2/15,1/2+4×1/3+7×2/15,5×1/3+7×2/15=1/10>0 by R3, R4, and R5. Suppose f3v=6 (as shown in Figure 1: (1–10)–(1–15)). In Figure 1, (1–12), (1–14), (1–15), ch′v≥9−4−2−max6×1/2,5×1/2+1/3+2/15,4×1/2+2×1/3+2×2/15,3×1/2+3×1/3+3×2/15,2×1/2+4×1/3+4×2/15=0 by R3, R4, and R5. Now, we consider Figure 1: (1–10), (1–11), and (1–13). By Lemma 3, f7+v≥1. By R5, the 7+-face gives no less than 3/8 to v. So, ch′v≥9−4+3/8−2−2/15−max6×1/2,5×1/2+1/3+2/15,4×1/2+2×1/3+2×2/15,3×1/2+3×1/3+3×2/15,2×1/2+4×1/3+4×2/15=29/120>0 by R3, R4, and R5. Suppose f3v=7 (as shown in Figure 1, (1–16), (1–17)), then, by Lemma 3, f7+v=2. By R5, each 7+-face gives no less than 3/8 to v. So, ch′v≥9−4+2×3/8−2−max7×1/2,6×1/2+1/3+2/155×1/2+2×1/3+2×2/15,4×1/2+3×1/3+3×2/15,3×1/2+4×1/3+4×2/15,2×1/2+5×1/3+5×2/15=1/4>0 by R3, R4, and R5.Suppose thatv be a 10-vertex. Obviously, f3v≤8 and it could be the 3-master of no more than two 3-vertices and the 2-master of no more than one 2-vertex. If f3v≤4, then by R3–R5, ch′v≥10−4−1−2−4×1/2−7×2/15=1/15>0. Let us discuss it in four ways.Firstly,f3v=5 (as shown in Figure 2, (2-1)–(2-15)). From the figure, (2-2)–(2-15), and obviously, ch′v≥10−4−1−2−5×1/2−3×2/15=1/10>0 by R3, R4, and R5. By Lemma 4, f7+v≥1 in figure (2-1). So, by R5, 7+-face gives no less than 3/8 to v. Therefore, by R3–R5 ch′v≥10−4+3/8−1−2−5×1/2−4×2/15=29/120>0.Secondly,f3v=6 (as shown in Figure 2, (2-16)–(2-27)). By Lemma 4, f7+v≥1. Hence, ch′v≥10−4+3/8−1−2−6×1/2−2×2/15=13/120>0 by R3–R5.Thirdly,f3v=7 (as shown in Figure 2, (2-28)–(2-33)). By Lemma 4, f7+v=2. Hence, ch′v≥10−4+2×3/8−1−2−7×1/2−2/15=7/60>0 by R3–R5.Fourthly,f3v=8 (as shown in Figure 2: (2-34)–(2-35)). Then, f7+v=2 by Lemma 4. Let v be a 2-master of a 2-vertex u; then, u must be incident with a 7+-face for G with no adjacent 7-cycles. So, ch′v≥10−4+2×3/8−1/2−2−8×1/2=1/4>0 by R3–R5.Suppose thatv be an 11-vertex. It follows that f3v≤9, and it could be the 3-master of no more than two 3-vertices and the 2-master of no more than one 2-vertex. If f3v≤5, then, by R3–R5, ch′v≥11−4−1−2−5×1/2−8×2/15=13/30>0. Let us discuss it in four ways.Firstly,f3v=6 (as shown in Figure 3, (3-1)–(3-25)). Obviously, by R3–R5, ch′v≥11−4−1−2−6×1/2−3×2/15=3/5>0.Secondly,f3v=7 (as shown in Figure 3, (3-26)–(3-40)). From Figure 3, (3-26)–(3-40), by R3–R5, ch′v≥11−4−1−2−7×1/2−2×2/15=7/30>0.Thirdly,f3v=8 (as shown in Figure 3, (3-41)–(3-46)). By Lemma 5, f7+v≥1 in Figure 3: (3-41) and (3-43). So, ch′v≥11−4+3/8−1−2−8×1/2−2/15=129/120>0 by R3, R4, and R5. In Figure 3, (3-42) and (3-44)–(3-46), ch′v≥11−4−1−2−8×1/2=0 by R3–R5.Fourthly,f3v=9 (as shown in the figure, (3-47)), then, by Lemma 5, f7+v=2. Hence, ch′v≥11−4+2×3/8−1−2−9×1/2=1/4>0 by R3–R5.Figure 3
Vertexv is a 11-vertex, the various cases of f3v≥6.



---

*Source: 6695833-2021-04-15.xml*