Bulletin of the
Korean Mathematical Society BKMS

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')\leq \alpha v(G')+\beta$ for each $G'\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$.

Keywords: ($1,\lambda$)-embedded graph, $\alpha$-linear graph, acyclic edge choosability

MSC numbers: 05C10, 05C15