(1,λ)-EMBEDDED GRAPHS AND THE ACYCLIC EDGE CHOOSABILITY

A (1 ; )-embedded graph is a graph that can be embedded on a surface with Euler characteristic so that each edge is crossed by at most one other edge. A graph G is called -linear if there exists an integral constant such that e( G ' ) v ( G ' ) + for each GG. In this paper, it is shown that every (1 ; )-embedded graph G is 4-linear for all possible , and is acyclicly edge-(3∆( G) + 70)-choosable for = 1 ; 2. In this paper, all graphs considered arenite, simple and undirected. We use V ( G), E( G), ( G) and ∆( G) to denote the vertex set, the edge set, the minimum degree and the maximum degree of a graph G, respectively. Let e( G) = j E( G) j and v( G) = j V ( G) j . Moreover, for an embedded graph G (i.e., a graph that can be embedded on a surface), by F ( G) we denote the face set of G. Let f ( G) = j F ( G) j . The girth g( G) of a graph G is the length of the shortest cycle of G. A k-, k + - and k -vertex (or face) is a vertex (or face) of