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

Upper Bounds on Minimum Balanced Bipartitions of Plane Graphs

作　　者：陈涛[1] 颜超[1] CHEN Tao;YAN Chao(Pujiang Institute, Nanjing Technology University, Nanjing 211112, China)

机构地区：[1]南京工业大学浦江学院基础教学部,江苏南京211112

出　　处：《数学的实践与认识》2017年第21期185-189,共5页Mathematics in Practice and Theory

基　　金：2016年南京工业大学浦江学院科研重点项目(njpj2016-1-01);江苏省高校自然科学基金(16KJB110011)

摘　　要：关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.There is a folk conjecture on minimum balanced bipartition problem of plane graphs： every plane graph of order has a balanced bipartition V1, V2 such that e（V1, V2） ≤ n. In this thesis, we prove that if Hamiltonian plane graph G（V1 E） of order n contains a nearly equilateral triangle, n ≥ 18, then G（V, E） admits a balanced bipartite subgraph G（V1, V2） such that e（V1, V2） ≤ n.

关 键 词：平面图 哈密尔顿圈 平衡二部图 

分 类 号：O157.5[理学—数学]