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


Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree
Authors:Enrique Garcia‐Moreno  Gelasio Salazar
Abstract:We show that if G has a minor M with maximum degree at most 4, then the crossing number of G in a surface Σ is at least one fourth the crossing number of M in Σ. We use this result to show that every graph embedded on the torus with representativity r ≥ 6 has Klein bottle crossing number at least ⌊2r/3⌋2/64. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 168–173, 2001
Keywords:crossing number  graph minors
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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