List Edge Coloring of Outer-1-planar Graphs
- PDF / 954,262 Bytes
- 16 Pages / 612 x 792 pts (letter) Page_size
- 68 Downloads / 181 Views
Acta Mathemacae Applicatae Sinica, English Series The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2020
List Edge Coloring of Outer-1-planar Graphs Xin ZHANG School of Mathematics and Statistics, Xidian University, Xi’an 710071, China (E-mail: [email protected])
Abstract A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once. It is known that the list edge chromatic number χ′l (G) of any outer-1-planar graph G with maximum degree ∆(G) ≥ 5 is exactly its maximum degree. In this paper, we prove χ′l (G) = ∆(G) for outer-1-planar graphs G with ∆(G) = 4 and with the crossing distance being at least 3. Keywords
outerplanar graph; outer-1-planar graph; crossing distance; list edge coloring
2000 MR Subject Classification
1
05C15; 05C10
Introduction
In this paper, all graphs are finite, simple and undirected. By V (G), E(G), δ(G) and ∆(G), we denote the vertex set, the edge set, the minimum degree and the maximum degree of a graph G, respectively. The order |G| of a graph G is |V (G)| and the size of G is |E(G)|. The distance dG (u, w) between two vertices u and w of a connected graph G is the minimum length of the path (i.e., the number of edges on the path) connecting them. The problem of coloring a graph arises in many practical areas such as pattern matching, sports scheduling, designing seating plans, exam timetabling, the scheduling of taxis, and solving Sudoku puzzles[9] . There are many types of colorings of graphs, and in this paper we mainly focus on the edge coloring. Precisely, an edge coloring of a graph G is an assignment of colors to the edges of G such that every pair of adjacent edges receive different colors. An edge k-coloring of a graph G is an edge coloring of G from a set of k colors. The minimum positive integer k for which G has an edge k-coloring, denoted by χ′ (G), is the edge chromatic number of G. The well-known Vizing’s Theorem states that ∆(G) ≤ χ′ (G) ≤ ∆(G) + 1 for any simple graph G. Suppose that a set L(e) of colors, called a list of e, is assigned to each edge e ∈ E(G). L-coloring an edge e means coloring e with a color in L(e). An edge L-coloring of G is an edge coloring c so that c(e) ∈ L(e) for every e ∈ E(G). We say that G is edge k-choosable if G has an edge L-coloring whenever |L(e)| = k for every e ∈ E(G). The minimum integer k for which G is edge k-choosable is the list edge chromatic number of G, denoted by χ′l (G). The most famous open problem concerning list edge coloring is probably the list edge coloring conjecture (LECC for short): χ′l (G) = χ′ (G) for any graph G. This conjecture has a fuzzy origin. Jensen and Toft overview its history in their book [6]. LECC is regarded to be very difficult, and is still widely open. Some partial results were however obtained in the special case of planar graphs. For example, LECC is true for planar graphs with maximum degree at least 12[3] , series-parallel graphs[7] , outerplanar graphs[11] , Manuscript received April 17, 2019. Accepted on
Data Loading...
