Bipartite subgraphs of integer weighted graphs (Q1381843)

For an integer-weighted graph \(G\), let \(f(G)\) denote the maximum total weight in a bipartite subgraph of \(G\). For every \(p>0\), let \(f(p)\) denote the minimum value of \(f(G)\), as \(G\) ranges over all integer-weighted graphs with total weight \(p\). The authors show that for every large \(n\) and every \(m<n\), one has \(f({n \choose 2} +m)= \lfloor {n^2 \over 4} \rfloor+ \min (\lceil {n\over 2} \rceil, f(m))\). This supplies the precise value of \(f(p)\) for many values of \(p\) including all \(p= {n \choose 2} +{m \choose 2}\) when \(n\) is large enough and \({m^2 \over 4} \leq{n \over 2}\).