平面图最小平衡二部划分的上界

作者：陈涛; 颜超

来源：数学的实践与认识, 2017, 47(21): 185-189.

• 平面图
• 哈密尔顿圈
• 平衡二部图

关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V1,V2)使得e(V1,V2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V1,V2)使得e(V1,V2)≤n.

• 单位
  南京工业大学浦江学院