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

A (1, ${\lambda}$ )-embedded graph is a graph that can be embedded on a surface with Euler characteristic ${\lambda}$ so that each edge is crossed by at most one other edge. A graph $G$ is called ${\alpha}$ -linear if there exists an integral constant ${\beta}$ such that $e(G^{\prime}){\leq}{\alpha}v(G^{\prime})+{\beta}$ for each $G^{\prime}{\subseteq}G$ . In this paper, it is shown that every (1, ${\lambda}$ )-embedded graph $G$ is 4-linear for all possible ${\lambda}$ , and is acyclicly edge-( $3{\Delta}(G)+70$ )-choosable for ${\lambda}$ = 1, 2.