Upper bounds on the bisection width of 3- and 4-regular graphs (Q849636)

New upper bounds are obtained for the bisection width of graphs that have a regular vertex degree. It is shown that the bisection width of sufficiently large 3-regular graphs with \(| V| \) vertices is at most \(( \frac{1}{6}+\varepsilon) | V| \), with \(\varepsilon >0\). For the bisection width of sufficiently large 4-regular graphs it is shown that \((\frac{2}{5}+\varepsilon) | V| \) is an upper bound, with \(\varepsilon >0\).