Uppre Bounds On Mimmum Balanced Bipartitions Of Plane Graphs

A balanced bipartition of a graph G is a partition of V(G) into two subsets V1, V2, which differ in size by at most1. The minimum balanced bipartition problem asks for a balanced bipartition V1, V2of a graph minimizing e(Vi, V2), where e(V1, V2) is the number of edges joining V1and V2. There is a folk conjecture on minimum balanced bipartition problem of plane graphs:every plane graph of order n has a balanced bipartition V1, V2such that e(V1, V2)≤n. Genghua Fan et al [8] prove that if G is a plane graph of order n containing no separating triangles, then G admits a balanced bipartition V1, V2such that e(V1, V2)≤n+1In this thesis, we investigate mainly the minimum balanced bipartition problem of plane graphs containing Hamilton cycle.In the first chapter of this thesis, we will introduce some basic definitions, present the history of balanced bipartition, and some known results. In Chapter2, we study the minimum balanced bipartition of Hamiltonian plane graph with nearly equilateral triangles which will be defined later. In Chapter3, we discuss the minimum balanced bipartition of bipartite Hamiltonian plane graphs. In the last chapter, we define an S-triangle and denote by d the difference between the longest edge and the shortest edge in S-triangle. We study the relation between the minimum balanced bipartition of S-triangle and d.