2-可平面图的交叉数及其应用

作者：张欣

来源：数学学报(中文版), 2021, 64(03): 463-470.

• 2-平面图
• 交叉数
• 权转移方法
• 完全图

图在平面内具有最小交叉次数的嵌入称为该图的一个最优平面画法.图G的交叉数cr(G)是该图的最优平面画法中的交叉次数.如果一个图可以嵌入在平面内使得每条边最多被交叉k次,则称其为k-可平面图.Zhang等人(2012)证明了顶点数为n的1-可平面图的交叉数最多为n-2,并且该上界是最优的.Czap,Harant与Hudak(2014)证明了顶点数为n的2-可平面图的交叉数最多为5(n-2).本文给出了2-可平面图的交叉数的一个更好的上界,并利用它从组合学的角度证明了Kn是2-可平面图当且仅当n≤7(该问题于2019年之前是个公开问题,最近由Angelini等人使用计算机程序证明).

• 单位
  西安电子科技大学