1014 J Comb Optim (2016) 31:1013–1022
1 Introduction
The theory of graph coloring has important application in combinatorial optimiza-
tion, web design, computer science and so on. Particularly, in files transmission of a
computer network, channel assignment, pattern matching, computation of Hessians
matrix. In this paper, we consider two important coloring, list edge coloring and list
total coloring, which arise in some practical problems concerning frequency assign-
ment. Here are some other interesting colorings, we refer the readers to Angelini and
Frati (2012); Bessy and Havet (2013); Du et al. (2004); Garg et al. (1996); Li et al.
(2013); Wang et al. (2014b,a)etc.
All graphs considered in this paper are simple. Let G be a planar graph and has
embedded in the plane. We use V (G), E(G), F(G), Δ(G) and δ(G) to denote the
vertex set, the edge set, the face set, the maximum degree and the minimum degree
of G, respectively. For a vertex v of G,thedegree d(v) denote the number of edges
incident with v, and for a face f of G,thedegree d( f ) denote the length of the boundary
walk of f . Denote by k-vertex the vertex of degree k,byk
−
-vertex the vertex of degree
at most k,byk
+
-vertex the vertex of degree at least k. If two cycles share at l east one
edge, we call them adjacent.Weusen
k
(v), f
k
(v) and n
k
( f ) to denote the number of
k-vertices adjacent to the vertex v, the number of k-faces incident with the vertex v,
and the number of k-vertices incident with the face f , respectively. In the following,
we shall introduce the notations of list total coloring and list edge coloring.
The problem of minimum number of choosability of graphs was first introduced
by Vizing (1976). Firstly, list total coloring is a type of coloring that combines list
coloring with total coloring. It is a choice of a color for each vertex or each edge, from
its list of allowed colors; the coloring is proper if no two adjacent or incident elements
receive the same color. Specifically, a mapping L is called to be a total assignment
for a graph G if it assigns a list L(x) of possible colors for each element x ∈ V ∪ E .
If G has a total coloring ϕ such that ϕ(x) ∈ L(x) for all x ∈ V ∪ E, and no two
adjacent or incident elements receive the same color, then we say that ϕ is a total-L
-coloring of G or G is total-L -colorable. A graph G is called total-k -choosable if it is
total-L-colorable for every total assignment L satisfying |L(x)|≥k for each element
x ∈ V ∪ E .Thelist total chromatic number χ
l
(G) of G is the smallest integer k
such that G is total-k-choosable. Similarly, the list edge chromatic number χ
l
(G) of
G can be defined in terms of coloring the edges alone. The ordinary edge chromatic
number of G are denoted by χ
(G). Obviously, it holds that χ
l
(G) ≥ χ
(G) ≥ Δ and
χ
l
(G) ≥ χ
(G) ≥ Δ + 1.
As far as list edge colorings and list total colorings are widely studied, quite a few
interesting results have been obtained in recent years. Firstly, we introduce a famous
conjecture.
Conjecture 1 (List Coloring Conjecture) For any graph G,
(a) χ
l
(G) = χ
(G);
(b) χ
l
(G) = χ
(G).
Part (a) of Conjecture 1 was formulated independently by a number of people,
including Vizing, Gupta, Albertson and Collins, Bollobás and Harris (see Hägkvist
123
