{
  "id": "1701.07162",
  "version": "v1",
  "published": "2017-01-25T05:03:42.000Z",
  "updated": "2017-01-25T05:03:42.000Z",
  "title": "On problems about judicious bipartitions of graphs",
  "authors": [
    "Yuliang Ji",
    "Jie Ma",
    "Juan Yan",
    "Xingxing Yu"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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)/2\\rfloor$ (rather than $(d_G(v)-1)/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\\geq 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)\\}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-25T05:03:42.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "judicious bipartitions",
      "correct lower bound",
      "graphic sequence",
      "balanced bipartite spanning subgraph",
      "study bipartitions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}