On balanced bipartitions of graphs. Issue 3 (1st September 2020) - Li, Guangnuan
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.