首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号