Bounds on the max and min bisection of random cubic and 4-regular graphs

In this paper we present simple randomized algorithms to bisect cubic and 4-regular graphs. These algorithms produce bisections of size asymptotically at most 0.17404n for typical random cubic n-vertex graphs, and n/3+eps n for random 4-regular (any eps>0). We also obtain asymptotic lower bounds for the size of the maximum bisection, for random cubic and random 4-regular graphs with $ vertices, of 1.32697 n and 5n/3+eps n, respectively. In all cases except the minimum bisection of cubic graphs, these give new results on the existence of regular graphs with small or large bisections. The randomized algorithms are derived from a greedy algorithm and the analysis is based on the differential equation method.Postprint (published version