Bipartite subgraphs of integer weighted graphs
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}\).
- Bipartite divisor graphs for integer subsets
- Bipartite subgraphs
- On Subgraphs of the Complete Bipartite Graph
- On bipartite graphs with weak density of some subgraphs
- Publication:4863503
- Bipartite Subgraphs of Triangle-Free Graphs
- Bipartite spanning sub(di)graphs induced by 2-partitions
- Bipartite subgraphs of triangle-free subcubic graphs
- Bipartite subgraphs of H-free graphs
- scientific article; zbMATH DE number 4053666
- Judicious \(k\)-partitions of graphs
- Maximum cuts and judicious partitions in graphs without short cycles
- Inverting the Turán problem with chromatic number
- Maximum bipartite subgraphs in graphs without short cycles
- Maximum bisections of graphs without cycles of length 4
- Maximum bisections of graphs without short even cycles
- Hypergraph cuts above the average
- On bisections of directed graphs
- Inverting the Turán problem
- The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
- On judicious partitions of uniform hypergraphs
- On a problem of Ahlswede and Katona
- Judicious partitions of bounded‐degree graphs
- Maximum cuts of graphs with forbidden cycles
- Problems and results on judicious partitions
- Judicious partitions of uniform hypergraphs
- BIPARTITE DIVISOR GRAPH FOR THE PRODUCT OF SUBSETS OF INTEGERS
- Maximum cuts in graphs without wheels
- Bipartite subgraphs of H-free graphs
- Lower bounds for max-cut in H-free graphs via semidefinite programming
- Minimum weight \(H\)-decompositions of graphs: the bipartite case
- Maximum bipartite subgraphs in H-free graphs
- On judicious bipartitions of graphs
- Making an H H‐free graph k k‐colorable
- Lower Bounds for Maximum Weighted Cut
- Maximum bisections of graphs without adjacent quadrilaterals
- On bipartite graphs with weak density of some subgraphs
- Max \(k\)-cut and judicious \(k\)-partitions
This page was built for publication: Bipartite subgraphs of integer weighted graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1381843)
