Graphic sequences have realizations containing bisections of large degree

✍ Scribed by Stephen G. Hartke; Tyler Seacrest

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 233 KB
• Volume: 71
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20652

✦ Synopsis

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