On problems about judicious bipartitions of graphs

Bollob'{a}s and Scott [5] conjectured that every graph $G$ has a balanced bipartite spanning subgraph $H$ such that for each $v\in V(G)$, $d_H(v)\ge (d_G(v)-1)/2$. In this paper, we show that every graphic sequence has a realization for which this Bollob'{a}s-Scott conjecture holds, confirming a conjecture of Hartke and Seacrest [10]. On the other hand, we give an infinite family of counterexamples to this Bollob'{a}s-Scott conjecture, which indicates that $\lfloor (d_G(v)-1)\mathrm{/}2\rfloor$ (rather than $(d_G(v)-1)\mathrm{/}2$) is probably the correct lower bound. We also study bipartitions $V_1,V_2$ of graphs with a fixed number of edges. We provide a (best possible) upper bound on $e(V_1{)}^{\lambda }+e(V_2{)}^{\lambda }$ for any real $\lambda \ge 1$ (the case $\lambda =2$ is a question of Scott [13]) and answer a question of Scott [13] on $\max \{e(V_1),e(V_2)\}$.