Graphic Sequences Have Realizations Containing Bisections of Large Degree
Stephen G. Hartke, Tyler Seacrest · Journal of Graph Theory · 2011
A bisection of a graph is a balanced bipartite spanning sub‐graph. Bollobás and Scott conjectured that every graph G has a bisection H such that deg H ( v ) ≥ ⌊deg G ( v )/2⌋ for all vertices v . We prove a degree sequence version of this conjecture: given a graphic sequence π, we show that π has a realization G containing a bisection H where deg H ( v ) ≥ ⌊(deg G ( v ) − 1)/2⌋ for all vertices v . This bound is very close to best possible. We use this result to provide evidence for a conjecture of Brualdi (Colloq. Int. CNRS, vol. 260, CNRS, Paris) and Busch et al. (2011), that if π and π − k are graphic sequences, then π has a realization containing k edge‐disjoint 1‐factors. We show that if the minimum entry δ in π is at least n /2 + 2, then π has a realization containing edge‐disjoint 1‐factors. We also give a construction showing the limits of our approach in proving this conjecture. © 2011 Wiley Periodicals, Inc. J Graph Theory