On balanced bipartitions of graphs. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Li, Guangnuan
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 1059
• Page End: 1062
• Publication Date: 2020-09-01
• Subjects: Bisection -- balanced bipartition -- degree sequence; 05C75
• DOI: 10.1016/j.akcej.2020.01.001
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: Bollobás and Scott conjectured that every graph G has a balanced bipartite spanning subgraph H such that for each v ∈ V ( G ), d H ( v ) ≥ ( d G ( v ) − 1 ) / 2, for each v ∈ V ( G ) . In this paper, we consider the contrary side and show that every graphic sequence has a realization G which admits a balanced bipartite spanning subgraph H such that d H ( v ) ≤ ⌈ ( d G ( v ) + 1 ) / 2 ⌉ for each v ∈ V ( G ), and we show that the bound is sharp.