# A Note on Edge-Group Choosability of Planar Graphs without 5-Cycles

Authors: Amir Khamseh
Journal: Journal of Mathematics
 (2020)

---

## Abstract

This paper is devoted to a study of the concept of edge-group choosability of graphs. We say thatG is edge-k-group choosable if its line graph is k-group choosable. In this paper, we study an edge-group choosability version of Vizing conjecture for planar graphs without 5-cycles and for planar graphs without noninduced 5-cycles (2010 Mathematics Subject Classification: 05C15, 05C20).


---

## Body

## 1. Introduction

We consider only simple graphs in this paper unless otherwise stated. For a graphG, we denote its vertex set, edge set, minimum degree, and maximum degree by VG, EG, δG, and ΔG, respectively. A plane graph is a particular drawing of a planar graph in the Euclidean plane. We denote the set of faces of a plane graph G by FG. For a plane graph G and f∈FG, we write f=u1u2⋯un if u1,u2,…,un are the vertices on the boundary walk of f enumerated clockwise. The degree of a face is the number of edges on the boundary walk. Let dGx, or simply dx, denote the degree of a vertex (or face) x in G. A vertex (or face) of degree k is called a k-vertex (or k-face). For v∈VG, NGv is the set of all vertices of G that are adjacent to v in G. We denote the line graph of a graph G by ℓG.Ak-coloring of a graph G is a mapping ϕ from VG to the set of colors 1,2,…,k such that ϕx≠ϕy for every edge xy. A graph G is k-colorable if it has a k-coloring. The chromatic numberχG is the smallest integer k such that G is k-colorable. A mapping L is said to be a list assignment for G if it supplies a list Lv of possible colors to each vertex v. A k-list assignment of G is a list assignment L with Lv=k for each vertex v∈VG. If G has some k-coloring ϕ such that ϕv∈Lv for each vertex v, then G is L-colorable or ϕ is an L-coloring of G. We say that G is k-choosable if it is L-colorable for every k-list assignmentL. The choice number or list chromatic numberχlG is the smallest k such that G is k-choosable. For edge-colorings of G, we can define analogous notions such as edge-k-colorability, edge-k-choosability, the chromatic indexχ′G, and the choice indexχl′G. Clearly, we have χ′G=χℓG and χl′G=χlℓG. The notion of list coloring of graphs has been introduced by Erdős et al. [1] and Vizing [2]. The following conjecture, which first appeared in [3], is well-known as the List Edge Coloring Conjecture.Conjecture 1.
IfG is a multigraph, then χl′G=χ′G.Although Conjecture1 has been proved for a few special cases such as bipartite multigraphs, complete graphs of odd order, multicircuits, graphs with ΔG≥12 that can be embedded in a surface of nonnegative characteristic, and outerplanar graphs, it is regarded as very difficult. Vizing proposed the following weaker conjecture (see [4]).Conjecture 2.
Every graphG is edge-ΔG+1-choosable.AssumeA is an Abelian group, and FG,A denotes the set of all functions f:EG⟶A. Consider an arbitrary orientation of G. The graph G is A-colorable if, for every f∈FG,A, there is a vertex coloring c:VG⟶A such that cx−cy≠fxy for each directed edge from x to y. The group chromatic number of G, χgG, is the minimum k such that G is A-colorable for any Abelian group A of order at least k. The notion of group coloring of graphs was first introduced by Jaeger et al. [5].The concept ofgroup choosability was introduced by Král and Nejedlý in [6], and some first results in this area were obtained in [7, 8]. Let A be an Abelian group of order at least k and L:VG⟶2A be a list assignment of G. For f∈FG,A, an A,L,f-coloring under an orientation D of G is an L-coloring c:VG⟶A such that cx−cy≠fxy for every edge e=xy, where e is directed from x to y. If for each f∈FG,A, there exists an A,L,f-coloring for G, and then we say that G is A,L-colorable. The graph G is k-group choosable if G is A,L-colorable for each Abelian group A of order at least k and any k-list assignmentL:VG⟶Ak. The minimum k for which G is k-group choosable is called the group choice number of G and is denoted by χglG. It is clear that the concept of group choosability is independent of the orientation on G. Graph G is called edge-k-group choosable if its line graph is k-group choosable. The group-choice index of G, χgl′G, is the smallest k such that G is edge-k-group choosable, i.e., χgl′G=χglℓG. It is easily seen that an even cycle is not edge-2-group choosable. This example shows that χgl′G is not generally equal to χ′G. But we can extend the Vizing conjecture as follows.Conjecture 3.
IfG is a multigraph, then χgl′G≤ΔG+1.SinceΔG≤χ′G≤ΔG+1, as a sufficient condition, we have the following weaker conjecture.Conjecture 4.
IfG is a multigraph, then χgl′G≤χ′G+1.Some early results concerning edge-group choosability of graphs were presented by the authors in a series of lectures in Annual Iranian Mathematical Conferences (see [9–11]). Conjecture 3 has been proved for graphs with maximum degree Δ≤3 [9], planar graphs with maximum degree Δ≥11 [9], planar graphs without 4-cycles with maximum degree Δ≥5 [11], outerplanar graphs [12], simple series-parallel graphs [12], K2c∧K1∪K2-minor-free graphs [12], and planar graphs with maximum degree ΔG=4 that has no cycles of length from 4 to 14 [10]. For further reference, we add here some related details.Theorem 1 (see [9]).
Letl be a natural number, v be a vertex of degree at most 2 of G, and e be an edge incident to v. If χgl′G−e≤ΔG+l, then χgl′G≤ΔG+l.Theorem 2 (see [9]).
LetG be a graph with χgl′G−e<χgl′G, for each e∈EG. Then, δℓG≥χgl′G−1.Theorem 3 (see [9]).
LetG be a graph with maximum degree ΔG. If ΔG≤3, then χgl′G≤ΔG+1, and if ΔG=4, then χgl′G≤6.Theorem 4 (see [7]).
(a)
LetPn and Cn denote a path and a cycle of length n, respectively. Then, χglPn=2 and χglCn=3.(b)
For any connected simple graphG, we have χglG≤ΔG+1, with equality holds if and only if G is either a cycle or a complete graph.Immediately from Theorem4, we see that χgl′Pn=ΔPn=2 and χgl′Cn=ΔCn+1=3. In this paper, we show that any planar graph G without 5-cycles with maximum degree Δ is edge-Δ+2-group choosable. If in addition ΔG≥6, we can show that G is edge-Δ+1-group choosable. This proves in advance that Conjecture 3 and, consequently, Conjecture 4 holds for this class of planar graphs. Moreover, we show that if G is a planar graph without noninduced 5-cycles, then χgl′G≤max7,Δ+2.


## 2. Main Results

First we need a lemma, which we will discuss below. It is a structural lemma for plane graphs without 5-cycles.Lemma 1 (see [13]).
If a plane graphG with δG≥3 has no five cycles, then there exists an edge xy of G such that dx=3 and dy≤5.Note thatG is a minimal counterexample to a theorem if G is a counterexample, that is, G satisfies the hypotheses but not the conclusion of the theorem, and there is no counterexample G′ satisfying either VG′<VG or VG′=VG and EG′<EG.Theorem 5.
IfG is a planar graph without 5-cycles with maximum degree Δ, then G is edge-Δ+2-group choosable.Proof. We saw in Theorem4 that if Pn and Cn denote a path and a cycle of length n, respectively, then χglPn=2 and χglCn=3. Moreover, for any connected simple graph G, we have χglG≤ΔG+1, with equality holds if and only if G is either a cycle or a complete graph. Immediately, we see that χgl′Pn=ΔPn=2 and χgl′Cn=ΔCn+1=3. Hence, if ΔG≤3, then χgl′G≤ΔG+1, and if ΔG=4, then χgl′G≤6. Here, we used the observation that, for a connected graph G, if ΔG=1, then G=P2; if ΔG=2, then G=Pn or G=Cn; if ΔG≤3, then ΔℓG≤4; and if ΔG≤4, then ΔℓG≤6. Now, let G be a minimal counterexample to Theorem 5 for some Abelian group A with A≥ΔG+2, a ΔG+2-list assignment L:VℓG⟶AΔG+2 and f∈FℓG,A. Then, G is connected, δG≥3, and ΔG≥5. By Lemma 1, there exists a vertex e∈VℓG with dℓGe≤6. Suppose that G′=G−e. Then, ℓG′=ℓG−e, and since χgl′G′≤Δ+2, there exists an A,L,f-coloring c:VℓG′⟶A. For each e′∈NℓGe we can consider, without loss of generality, ee′ to be directed from e to e′. Then, since Le=Δ+2≥7 and dℓGe≤6, Le−ce′+fee′:e′∈NℓGe≥1. In other words, there is at least one color available to color e. Thus, we can color all edges of G. This contradiction completes the proof of theorem.The above proof shows that the only critical case isΔ=5. If remove it, we can prove a stronger result.Theorem 6.
IfG is a planar graph with maximum degree Δ≥6 and without 5-cycles, then χgl′G≤Δ+1.Proof. LetG be a minimal counterexample to this theorem for some Abelian group A with A≥ΔG+1, a ΔG+1-list assignment L:VℓG⟶AΔG+1 and f∈FℓG,A. Then, δG≥3. By Lemma 1, there exists a vertex e∈VℓG with dℓGe≤6. Suppose that G′=G−e. Then, ℓG′=ℓG−e, and since χgl′G′≤Δ+1, there exists an A,L,f-coloring c:VℓG′⟶A. For each e′∈NℓGe, we can consider, without loss of generality, ee′ to be directed from e to e′. Then, since Le=Δ+1≥7 and dℓGe≤6, Le−ce′+fee′:e′∈NℓGe≥1. In other words, there is at least one color available to color e. Thus, we can color all edges of G. This contradiction completes the proof of theorem.The structure of planar graphs without noninduced 5-cycles is given in the following lemma.Lemma 2 (see [14]).
LetG be a planar graph without noninduced 5-cycles. Then, G contains one of the following configurations:(1)
An edgeuv with du+dv≤max8,ΔG+2(2)
An even cycleC:v1,v2,…,v2n with dv1=dv3=⋯=dv2n−1=3 and dv2=dv4=⋯=dv2n=ΔGTheorem 7.
IfG is a planar graph without noninduced 5-cycles, then(1)χgl′G≤max7,Δ+2.Proof. Using Lemma 2, the proof is straightforward and is similar to the proof of Theorem 5. We leave the details to the reader.If a planar graphG without noninduced 5-cycles in addition contains no even cycles, we can replace Δ+2 by Δ+1 in Theorem 7.Theorem 8.
IfG is a planar graph without noninduced 5-cycles and without even cycle C:v1,v2,…,v2n with dv1=dv3=⋯=dv2n−1=3 and dv2=dv4=⋯=dv2n=ΔG, then χgl′G≤max7,Δ+1.Proof. Let k=max7,Δ+1 and G be a minimal counterexample to this theorem for some Abelian group A with A≥k, a k-list assignmentL:VℓG⟶Ak and f∈FℓG,A. By Theorem 1 and Lemma 2, there exists a vertex e∈VℓG with dℓGe≤Δ. Suppose that G′=G−e. Then, ℓG′=ℓG−e, and since χgl′G′≤Δ+1, there exists an A,L,f-coloring c:VℓG′⟶A. For each e′∈NℓGe, we can consider, without loss of generality, ee′ to be directed from e to e′. Then, since Le≥Δ+1 and dℓGe≤Δ, Le−ce′+fee′:e′∈NℓGe≥1. In other words, there is at least one color available to color e. Thus, we can color all edges of G. This contradiction completes the proof of theorem.



---

*Source: 4639260-2020-10-22.xml*