A balanced bipartition of a graph $G(V,E)$ is a bipartition $V_{1}$ and $V_{2}$ of V(G) such that $||V_{1}|-|V_{2}||\leq 1$. The minimum balanced bipartition problem asks for a balanced bipartition minimizing $e(V_{1},V_{2})$, where $e(V_{1},V_{2})$ is the number of edges joining $V_{1}$ and $V_{2}$. In this paper, for Hamilton plane graphs, we study the relation between upper bounds on the minimum of $e(V_{1},V_{2})$ and $d$, which is the difference between the maximum edge function value and the minimum edge function value of Perfect-inner triangle.
[1] Garey M R, Johnson D S, Stockmeyer L J. Some simplified NP-complete graph problems[J]. Theoretical computer Science, 1976, 1:237-267.
[2] Bollobás B, Scott A D. Judicious partitions of bounded-degree graphs[J]. Graph Theory, 2004, 46:131-143.
[3] Edwards C S. Some extremal properties of bipartite subgraphs[J]. Canadian Journal of Mathematics, 1973, 25:475-485.
[4] Bollobás B, Scott A D. Judicious partitions of graph[J]. Periodica Mathematica Hungarica, 1993, 26(2):125-137.
[5] Karpinski M. On approximability of minimum bisection problem[J]. Electronic Colloquium on Computational Complexity, 2002, 46:225-238.
[6] Lee C, Loh P, Sudakov B. Bisection of graphs[J]. Journal of Combinatorial Theory Series B, 2013, 103:599-629.
[7] Li H Y, Liang Y, Liu M H, et al. On minimum balanced bipartitions of triangle-free graphs[J]. Journal of Combinatorial Optimization 2014, 27:557-566.
[8] Bollobás B, Scott A D. Problems and results on judicious partitions[J]. Random Structures Algorithms, 2002, 21:414-430.
[9] Xu B G, Yan J, Yu X X. Balanced judicious bipartition of graphs[J]. Graph Theory, 2010, 63:210-225.
[10] Xu B G, Yan J, Yu X X. A note on balanced bipartitions[J]. Discrete Math, 2010, 310:2613-2617.
[11] Xu B G, Yu X X. On judicious bisections of graphs[J]. Journal of Combinatorial Theory Series B, 2014, 106:30-69.
[12] 许宝刚. Graph partitions:rencent progresses and some open problems[J]. 数学进展, 2016, 45:1-20.
[13] Fan G H, Xu B G, Yu X X, et al. Upper bounds on minimum balanced bipartitions[J]. Discrete Mathematics, 2012, 312:1077-1083.
[14] Whitney H. A theorem on graphs[J]. Annals of Mathematics, 1931, 32:378-390.
