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

Upper Bounds on Minimum Balanced Bipartitions of Plane Graphs

关于平面图的平衡二部子图的研究有一个猜想:任意一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.