A structural theorem on embedded graphs and its application to colorings |
| |
Authors: | Bao Gang Xu Xiao Xu Lu |
| |
Institution: | (1) Nanjing Normal University, 122 Ninghai Road, Nanjing, 210097, P. R. China |
| |
Abstract: | In this paper, a Lebesgue type theorem on the structure of graphs embedded in the surface of characteristic σ ≤ 0 is given, that generalizes a result of Borodin on plane graphs. As a consequence, it is proved that every such graph
without i-circuits for 4 ≤ i ≤ 11 − 3σ is 3-choosable, that offers a new upper bound to a question of Y. Zhao.
Research supported by NSFC |
| |
Keywords: | circuit embedded graph coloring |
本文献已被 维普 SpringerLink 等数据库收录! |
|