Applied Science and Innovative Research 

ISSN 2474-4972 (Print) ISSN 2474-4980 (Online) 

Vol. 3, No. 2, 2019 

www.scholink.org/ojs/index.php/asir 

85 
 

Original Paper 

List Edge Colorings of Planar Graphs with 7-cycles Containing at 

Most Two Chords 

Wenwen Zhang1* 

1 School of Date and Computer Science, Shandong Women’s University, Jinan, 250300, China 

 

Received: May 5, 2019          Accepted: May 19, 2019        Online Published: May 27, 2019 

doi:10.22158/asir.v3n2p85       URL: http://dx.doi.org/10.22158/asir.v3n2p85 

 

Abstract 

In this paper we prove that if G is a planar graph, and each 7-cycle contains at most two chords, then 

G is edge-k-choosable, where k = max{8, ∆(G) + 1}. 

Keywords 

List edge coloring, planar graph, cycle 

 

1. Introduction 

All graphs considered here are finite, simple and undirected. Let G be a graph with vertex set V (G) and 

edge set E(G). For vertex v ∈ V (G), let E(v) be the set of edges incident with v. The degree of v in G, 

denoted d(v), is the cardinality of E(v). A k-vertex, k−-vertex or k+-vertex is a vertex of degree k, at most 

k or at least k, respectively. We denote the maximum degree of G by ∆(G) and minimum degree of G by 

δ(G). A k (or k+)-vertex adjacent to a vertex x is called a k (or k+)-neighbor of x. A k-cycle is a cycle of 

length k. Given a cycle C of length k in G, an edge xy ∈ E(G)\E(C) is called a chord of C if x, y ∈ V 

(C). Such a cycle C is also called a chordal-k-cycle. 

Let G be a plane graph, F (G) be the face set of G. The degree of a face f, denoted by dG(f) is the 

number of edges incident with f where each cut edge is counted twice. A k-, k+-face is a face of degree k, 

at least k. A k-face of G is called an (i
1
, i

2
, … , i

k
)-face if the vertices in its boundary are of degrees i

1
, 

i
2
, … , i

k respectively. For a vertex v ∈ V (G), we denote by fk (v) the number of k-faces incident with 

v. 

A graph is k-edge-colorable, if its edges can be colored with k colors such that adjacent edges receive 

different colors. The edge chromatic number of a graph G, denoted by χ'(G), is the smallest integer k 

such that G is k-edge-colorable. We say that L is an edge assignment for G if it assigns a list L(e) of 

colors to each edge e of G. If G has a proper edge-coloring φ such that φ(e) ∈ L(e) for each edge e of 

G, then we say that G is edge-L-colorable and φ is an edge-L-coloring of G. The graph G is 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 3, No. 2, 2019 

86 
Published by SCHOLINK INC. 

edge-k-choosable if it is edge-L-colorable for every edge assignment L satisfying |L(e)| ≥ k for each 

edge e ∈ E(G), where k is a positive integer. The list-edge-chromatic-number χ'L (G) of G is the 

smallest k such that G is edge-k-choosable. 

List edge coloring was introduced by Vizing (Haggkvist & Chetwynd, 1992), later Bollobas and Harris 

(1985). They posed the following conjecture which is called the List Coloring Conjecture. 

Conjecture 1. For any multigraph G, χ'L (G) = χ' (G). 

Conjecture 1 was verified for some special classes of graphs, including bipartite multigraphs (Galvin, 

1995), complete graphs of odd order (Haggkvist & Janssen, 1997), multicircuits (Woodall, 1999), 

graphs with ∆(G) ≥ 12 which can be embedded in a surface of non-negative characteristic (Borodin, 

Kostochka, & Woodall, 1997), and outer planar graphs (Wang & Lih, 2001). Vizing (see Kostochka, 

1992) proposed a weaker conjecture as follows. 

Conjecture 2. Every graph G is edge-(∆(G) + 1)-choosable. 

Harris (n.d.) proved that χ'L (G) ≤ 2∆(G) − 2 if G is a graph with ∆(G) ≥ 3. This implies Conjecture 2 

for the case ∆(G) = 3. Juvan et al. (1999) settled the case for ∆(G) = 4. Conjecture 2 was verified for 

some special classes of graphs, including complete graphs (Haggkvist & Janssen, 1997), graphs with 

girth at least 8∆(ln ∆ + 1.1) (Haggkvist & Chetwynd, 1992), planar graphs with ∆ ≥ 8 (Bonamy, 2015). 

For planar graphs with some local conditions, see Hou, Liu and Cai (2009), Ma, Wang, Cai and Zhang 

(2011), Wang and Wu (2018). 

Ca, Ge, Zhang and Liu (2011) proved that if G is a planar graph without chordal 7-cycles, then G is 

edge-k-choosable, where k = max{8, ∆(G) + 1}. In this paper, we will extend this result to planar 

graphs in which all 7-cycles contain at most two chords and get the following theorem. 

Theorem 3. Let G be a planar graph in which each 7-cycle contains at most two chords. Then G is 

edge-k-choosable, where k = max{8, ∆(G) + 1}. 

 

2. Structural Properties of Planar Graphs with 7-Cycles Containing at Most Two Chords 

Lemma 4. Let G be a planar graph in which each 7-cycle contains at most two chords. Then at least 

one of the following holds. 

(1) G has an edge uv with d(u) + d(v) ≤ max{9, ∆(G) + 2}; 

(2) G has an even cycle C = v1v2...v2nv1 with d(v1) = d(v3) = ... = d(v2n−1) = 3. 

Proof. Since every planar graph with maximum degree ∆(G) ≥ 8 has chromatic index ∆(G)+1 (see 

Bonamy, 2015), we assume that ∆(G) ≤ 7 in the following proof. Suppose that G is a minimum 

counterexample to Lemma 4 in terms of the sums of the number of vertices and edges. It is obvious that 

G is connected. By the choice of G, we have there observations. 

(a) By the assumption, for any edge uv, d(u) + d(v) ≥ max{10, ∆(G) + 3} since (1) does not hold. So 

δ(G) ≥ 3 and all 3-vertices must be adjacent to maximum degree vertices. Besides, any 4-vertex is only 

adjacent to vertices of degree at least ∆(G) − 1. 

(b) Since G contains no 7-cycles with three chords, so for any 6+ -vertex v ∈ V (G), v is not incident 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 3, No. 2, 2019 

87 
Published by SCHOLINK INC. 

 

with five 3-faces f1, f2, f3, f4, f5 such that fi and fi + 1 are adjacent for all i = 1, 2, 3, 4. Then f3(v) ≤ 

[
4

5
d(v)]. 

(c) Let G
3 be the subgraph induced by the edges incident with all 3-vertices of G. Then G

3 is a forest 

and it contains a bipartite subgraph G' = (V1, V2) with two partite sets V1 and V2, such that dG' (v) = 2 for 

each vertex v ∈ V1 and dG' (v) = 1 for each vertex v ∈ V2. If uv ∈ G' and dG(u) = 3, then v is 

called a 3-master of u and u is called a dependent of v. Note that every 3-vertex has exactly two 

3-masters and each 7+-vertex can be the 3-master of at most one 3-vertex. 

Next we show that (c) is true. By (a), any two 3-vertices are not adjacent, that is, G3 does not contain 

odd cycles. Thus G
3 is a bipartite graph with partite sets V

1
, V

2
, so that V (G) = V1 U V2 and for each 

vertex v ∈ V1, dG(v) = 3; for each vertex v ∈ V2, dG(v) = ∆. Since G does not satisfy (2), G3 contains 

no even cycles. So G3 is a forest. For any component of G3, we select a vertex u with dG(u) = 3 as the 

root of the tree. Thus, every 3-vertex has exactly two children. We obtain G' by letting V
2 = {v : v is a 

child of a 3-vertex} and E(G') = {uv : u is 3-vertex and v is a child of u}. So (c) holds. 

Since G has properties (a), and G contains no 7-cycles with three chords. Suppose that v is a 5-vertex in 

G. Then we can get the following observations easily:  

(O1) If f
3
(v) = 4 and f

4
(v) = 1 (as in Figure 1), then f

5
+ (v

1
) ≥ 2; 

(O2) If f
3
(v) = 5 and f

4
(v) = 1, then for any neighbor x of v, f

5
+ (x) ≥ 2. 

Suppose that G is embedded in the plane. By Euler’s formula |V (G)|−|E(G)|+|F (G)| = 2, we have 

∑ (𝑑(𝑥) − 4) + ∑ (𝑑(𝑥) − 4) = −8 < 0

𝑥∈𝐹(𝐺)𝑥∈𝑉(𝐺)

 

We define ch to be the initial charge. Let ch(x) = d(x) − 4 for each x ∈ V ∪ F. So ∑ 𝑐ℎ(𝑥) <𝑥∈𝑉∪𝐹

0. Then we apply the following rules to redistribute the initial charge that leads to a new charge ch' (x) 

to each x ∈ V ∪ F. Since our rules only move charges around, and do not affect the sum. If we can 

show that ch' (x) ≥ 0 for each x, then we get an obvious contradiction, 0 ≤ ∑ 𝑐ℎ′(𝑥) =𝑥∈𝑉∪𝐹

∑ 𝑐ℎ(𝑥) < 0𝑥∈𝑉∪𝐹 . which completes our proof. 

 

 

Figure 1. Black Vertices do not Have Neighbors Other than Presented in the Picture, White 

Vertices can be Adjacent to Some Other Vertices 

 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 3, No. 2, 2019 

88 
Published by SCHOLINK INC. 

The discharging rules are defined as follows. 

R1. Every 3-vertex receives 
1

2
 from each of its two 3-masters. 

R2. Let f be a 3-face uvw and assume that d(u) ≤ d(v) ≤ d(w). 

R2.1 If d(u) = 3 or 4, then f receives 
1

2
 from v and w respectively; 

R2.2 If d(u) ≥ 5, then f receives 
1

3
 from u, v and w respectively. 

R3. Let f be a 5+-face and t the number of 5-vertices satisfying f3(v) = 4 on f. 

R3.1 If t = 0, then every of vertices incident with f receives 
𝑑(𝑓)−4

𝑑(𝑓)
 from f; 

R3.2 Otherwise t ≥ 1. Suppose v is such a vertex, then the every of remaining vertices incident 

with f receives 
𝑑(𝑓)−4

𝑑(𝑓)−2
 from f besides its two neighbors on f. 

R4. Let v be a 5-vertex. 

R4.1 If f3(v) = 4 and f4(v) = 1 (as in Figure 1), then v receives at least 
1

3
 from w by (O1); 

R4.2 If f3(v) = 5, then v receives 
1

5
 from each of the neighbors by (O2). 

Now, let’s begin to check ch'(x) ≥ 0 for all x ∈ V ∪ F. Let f ∈ F (G). Then d(f) ≥ 3. If d(f) = 3, 

then ch'(f) = ch(f)+min{2×
1

2
 , 3×

1

3
} = 0 by R2. If d(f) = 4, then ch'(f) = ch(f) =0. If d(f) ≥ 5, then ch'(f) ≥ 

ch(f )−
𝑑(𝑓)−4

𝑑(𝑓)
×d(f ) = 0 or ch'(f ) ≥ ch(f )− 

𝑑(𝑓)−4

𝑑(𝑓)−2
×(d(f )−2) = 0 by R3. 

Let v ∈ V (G). Then d(v) ≥ 3. If d(v) = 3, then v is exactly adjacent to two 3-masters, so ch'(v) = ch(v) 

+ 2 × 
1

2
 = 0 by R1. If d(v) = 4, then ch'(v) ≥ 0 + min{0, 

𝑑(𝑓)−4

𝑑(𝑓)−2
, 

𝑑(𝑓)−4

𝑑(𝑓)
} = 0 by R3. 

In the following we check the cases that d(v) = 5, 6, 7. 

Case 1. Let v be a 5-vertex. Then ch(v) = 1 and all neighbors of 5-vertex should be 5+-vertices by (a). 

If f3(v) = 5, then v receives 
1

5
 by R4.2. So ch'(v) ≥ 1+5× 

1

5
 −5× 

1

3
 = 

1

3
 > 0 by R2. Suppose that f3(v) = 

4. If the remaining face is a 4-face (as Figure 1), then ch'(v) ≥ 1 − 4 × 
1

3
 + 

1

3
 = 0 by R2 and R4.1; 

otherwise the remaining face is a 5+-face. Then v receives 
𝑑(𝑓)−4

𝑑(𝑓)−2
 ≥ 

1

3
 from the 5+-face by R3.2. So 

ch'(v) ≥ 1 − 4 × 
1

3
 + 

𝑑(𝑓)−4

𝑑(𝑓)−2
 ≥ 0 by R2 and R3.2. 

If f3(v) ≤ 3, then v may send some charge to its 5-neighbors. So there are two subcases. 

Subcase 2.1 v sends no charge to some 5-neighbor.  

Then ch'(v) ≥ 1 − 3 × 
1

3
 = 0 by R2. 

Subcase 2.2 v sends some charge to some 5-neighbor. 

Suppose that v is adjacent to a 5-vertex w such that f3(w) = 4 and f4(w) = 1 (as in Figure 1), then f3(v) ≤ 

2, f4(v) = 1 and f5+ (v) = 2. So ch'(v) ≥ 1 − 2 × 
1

3
 − 

1

3
 = 0 by R2 and R4.1. 

Suppose that v is adjacent to a 5-vertex w such that f3(w) = 5. Then f3(v) ≤ 3, f5+ (v) ≥ 2 and each 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 3, No. 2, 2019 

89 
Published by SCHOLINK INC. 

5 

 

5+-face sends at least 
1

5
 to v by R3. So ch'(v) ≥ 1 + 2 ×

1

5
 − 3 ×

1

3
 − 

1

5
 = 

1

5
 > 0 by R2 and R4.2. 

Case 2. Let v be a 6-vertex. Then ch(v) = 2, f3(v) ≤ 4 by (b). 

If v is not adjacent to a 5-vertex w such that f3(w) = 4 and f4(w) = 1 or f3(w) = 5, then v sends no charge 

to its 5-neighbors, so ch'(v) ≥ 2 − 4 × max{
1

3
, 

1

2
} = 0 by R3. 

Suppose that v is adjacent to a 5-vertex w such that f3(w) = 4 and f4(w) = 1 (as in Figure 1). Note that v 

is adjacent to only one such vertex w because each 7-cycle contains at most two chords in G. Then f3(v) 

≤ 3, f4(v) = 1 and f5+ (v) = 2. So ch'(v) ≥ 2 − 3 ×
1

2
 − 

1

3
 = 

1

6
 > 0 by R2 and R4.1. 

Suppose that v is adjacent to a 5-vertex w such that f3(w) = 5. Note that v may be adjacent to two such 

vertices. Then f3(v) ≤ 4 and f5+ (v) ≥ 2. So ch'(v) ≥ 2+2×
1

5
 −2×

1

3
 −2×

1

2
 −2×

1

3
 = 

1

15
 > 0 by R2, R3.1 

and R4.2. 

Case 3. Let v be a 7-vertex. Then ch(v) = 3, f
3
(v) ≤ 5 by (b). 

If v is not adjacent to a 5-vertex w such that f3(w) = 4 and f4(w) = 1 or f3(w) = 5, then v sends no charge 

to its 5-neighbors, so ch'(v) ≥ 3 − 5 × max{
1

3
, 

1

2
} − 

1

2
 = 0 by R1 and R2. 

Suppose that v is adjacent to a 5-vertex w such that f3(w) = 4 and f4(w) = 1 (as in Figure 1). Now f3(v) ≤ 

4 and v is adjacent to at most two such vertices because each 7-cycle contains at most two chords in G. 

So ch'(v) ≥ 3 − 2 ×
1

2
 − 2 ×

1

3
 − 

1

2
 − 2 ×

1

3
 = 

1

6
 > 0 by R1, R2 and R4.1. 

Suppose that v is adjacent to a 5-vertex w such that f3(w) = 5. Note that v may be adjacent to two such 

vertices. Then f3(v) ≤ 5 and f5+ (v) ≥ 2. So ch'(v) ≥ 3 + 2 ×
1

5
 − 2 ×

1

3
 − 3 × 

1

2
 − 

1

2
 − 2 × 

1

3
 = 

1

15
 > 0 by 

R1, R2, R3.1 and R4.2. 

 

3. Proof of Theorem 3 

Proof. The proof is carried out by contradiction. Suppose that G is a counterexample to our theorem 

with the minimum number of edges and G is any planar graph in which every 7-cycle contains at most 

two chords. Then there is an edge assignment L with |L(e)| ≥ k for all e ∈ E(G), where k = max{8, 

∆(G) + 1}, such that G is not edge-L-colorable. By Lemma 4, we consider two cases as follows. 

Case 1. G contains an edge uv with d(u) + d(v) ≤ max{9, ∆(G) + 2}. Consider the graph G' = G − uv. 

By inductive hypothesis, G has an edge-L- coloring φ, where L is an edge assignment with |L(e)| ≥ k for 

all e ∈ E(G') and k = max{8, ∆(G') + 1}. Since there exist at most max{7, ∆(G)} edges adjacent in G 

to uv and |L(uv)| ≥ max{8, ∆(G) + 1}, we can color uv with some color from L(uv) that was not used by 

φ on the edges adjacent to uv. It is easy to see that the resulting coloring is an edge-L-coloring of G. 

Case 2. G contains an even cycle c = v1v2...v2nv1 with d(v1) = d(v3) = ... = d(v2n−1) = 3. Let G' be the 

subgraph of G obtained by deleting the edges of C. By inductive hypothesis, G' has an edge-L-coloring 

φ, where L is an edge assignment with |L(e)| ≥ k for all e ∈ E(G) and k = max{8, ∆(G) + 1}. Define a 

new edge assignment L' (e) of C such that L' (e) = L(e) \ {φ(e' )|e'∈ E(G') is adjacent to e in G} for 

each e ∈ E(C). It is easy to see that |L' (e)| ≥ 2 for each e ∈ E(C). It follows from Erdős et al. (1979) 

that an even cycle is edge-2-choosable (since an even cycle is also a bipartite graph). So C is 

edge-L-colorable and it follows that G is edge-L-colorable. This completes the proof of Theorem 3. 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 3, No. 2, 2019 

90 
Published by SCHOLINK INC. 

Acknowledgements 

This work was partially supported by Shandong Provincial Natural Science Foundation, China 

(No.ZR2017BA009), A project of Shandong province higher educational Science and Technology 

Program (No.J17KA168) and Talent introduction research project of Shangdong Woman’s University 

(No.2016YJRC12). 

 

References 

Bollobas, B., & Harris, A. J. (1985). List-colourings of graphs. Graph Comb., 1, 115-127. 

https://doi.org/10.1007/BF02582936 

Bonamy, M. (2015). Planar graphs with ∆ ≥ 8 are(∆ + 1)-edge-choosable. SIAM J Discrete Math, 29, 

1735-1763. https://doi.org/10.1137/130927449 

Borodin, O. V., Kostochka, A. V., & Woodall. D. R. (1997). List edge and list total colourings of multi- 

graphs. J. Comb. Theory Ser. B., 71, 184-204. https://doi.org/10.1006/jctb.1997.1780 

Ca, J. S., Ge, L. S., Zhang, X., & Liu, G. Z. (2011). Edge-choosability of planar graphs without chordal 

7-cycles. Ars Combinatoria, 100, 169-176. 

Erdős, P., Rubin, A. L., & Taylor, H. (1979). Choosability in graphs. Congr Numer, 26, 125-157. 

Galvin, F. (1995). The list chromatic index of a bipartite multigraph. J. Comb. Theory Ser. B., 63, 

153-158. https://doi.org/10.1006/jctb.1995.1011 

Haggkvist, R., & Chetwynd A. (1992). Some upper bounds on the total and list chromatic numbers of 

multi graphs. J. Graph Theory, 16, 503-516. https://doi.org/10.1002/jgt.3190160510 

Haggkvist, R., & Janssen, J. (1997). New bounds on the list-chromatic index of the complete graph and 

other simple graphs. Comb. Probab. Comput., 6, 295-313. 

https://doi.org/10.1017/S0963548397002927 

Harris, A. J. (n.d.). Problems and conjectures in extremal graph theory (Ph.D. Dissertation). Cambridge 

University, UK. 

Hou, J. F., Liu, G. Z., & Cai, J. S. (2009). Edge-choosability of planar graphs without adjacent triangles 

or without 7-cycles. Discrete Math, 309, 77-84. https://doi.org/10.1016/j.disc.2007.12.046 

Juvan, M., Mohar, B., & Srekovski, R. (1999). Graphs of degree 4 are 5-choosable. J Graph Theory, 32, 

250-262. https://doi.org/10.1002/(SICI)1097-0118(199911)32:3%3C250::AID-JGT5%3E3.0.CO; 

2-R 

Kostochka, A. V. (1992). List edge chromatic number of graphs with large girth. Discrete Math, 101, 

189-201. https://doi.org/10.1016/0012-365X(92)90602-C 

Ma, Q. L., Wang, J. H., Cai, J. S., & Zhang, S. M. (2011). A note on edge-choosability of planar graphs 

without intersecting 4-cycles. J Appl Math Comput, 36, 367-372. 

https://doi.org/10.1007/s12190-010-0408-5 

Wang, H. Y., & Wu, J. L. (2018). List-edge-coloring of planar graphs without 6-cycles with three 

chords, J Comb Optim, 35, 555-562. https://doi.org/10.1007/s10878-017-0193-2 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 3, No. 2, 2019 

91 
Published by SCHOLINK INC. 

Wang, W. F., & Lih, K. W. (2001). Choosability, edge choosability and total choosability of 

outerpla-nar graphs. Eur. J. Comb., 22, 71-78. https://doi.org/10.1006/eujc.2000.0430 

Woodall, D. R. (1999). Edge-choosability of multicircuits. Discrete Math, 202, 271-277. 

https://doi.org/10.1016/S0012-365X(98)00297-0