(1,λ)-embedded graphs and the acyclic edge choosability
arXiv:1106.4681
Abstract
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') \leq α v(G')+β for each G'\subseteq G. 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.
Please cite this paper as X. Zhang, G. Liu, J.-L. Wu, (1,λ)-embedded graphs and the acyclic edge choosability, Bulletin of the Korean Mathematical Society, to appear