2017/01/25 by Ji, Yuliang, Ma, Jie, Yan, Juan +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1701.07162
Bollobás and Scott [5] conjectured that every graph G has a balanced bipartite spanning subgraph H such that for each v∈ V(G), dH(v)≥ (dG(v)-1)/2. In this paper, we show that every graphic sequence has a realization for which this Bollobá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ás-Scott conjecture, which indicates that \lfloor (dG(v)-1)/2\rfloor (rather than (dG(v)-1)/2) is probably the correct lower bound. We also study bipartitions V1, V2 of graphs with a fixed number of edges. We provide a (best possible) upper bound on e(V1)λ+e(V2)λ for any real λ≥ 1 (the case λ=2 is a question of Scott [13]) and answer a question of Scott [13] on max\e(V1),e(V2)\.