(1, λ)-EMBEDDED GRAPHS AND THE ACYCLIC EDGE CHOOSABILITY
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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^{\prime}){\leq}{\alpha}v(G^{\prime})+{\beta}$ for each $G^{\prime}{\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{\Delta}(G)+70$)-choosable for λ = 1, 2.
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^{\prime}){\leq}{\alpha}v(G^{\prime})+{\beta}$ for each $G^{\prime}{\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{\Delta}(G)+70$)-choosable for λ = 1, 2.
참고문헌 (11)
- N. Alon, "Acyclic coloring of graphs", Random Structures Algorithms, 2(3), pp.277~288 (1991)
- N. Alon, "Acyclic edge-colorings of graphs", J. Graph Theory, 37(3), pp.157~167 (2001)
- J. A. Bondy, "Graph Theory with Applications" (1976), North-Holland
- T. F. Coleman, "The cyclic coloring problem and estimation of sparse Hessian matrices", SIAM J. Algebraic Discrete Methods, 7(2), pp.221~235 (1986)
- T. F. Coleman, "Estimation of sparse Hessian matrices and graph coloring problems", Math. Programming, 28(3), pp.243~270 (1984)
- I. Fabrici, "The structure of 1-planar graphs", Discrete Math, 307(7), pp.854~865 (2007)
- A. Fiedorowicz, "About acyclic edge colourings of planar graphs", Inform. Process. Lett, 108(6), pp.412~417 (2008)
- B. Grunbaum, "Acyclic colorings of planar graphs", Israel J. Math, 14, pp.390~408 (1973)
- M. Molloy, "Further algorithmic aspects of the local lemma", it Pro- ceedings of the 30th Annual ACM Symposium on Theory of Computing, pp.524~529 (1998)
- "Improved bounds on coloring of graphs"[URL]
- G. Ringel, "Ein sechsfarbenproblem auf der Kugel", Abh. Math. Sem. Univ. Hamburg, 29, pp.107~117 (1965)