It was proved by \textit{C. S. Edwards} [Can. J. Math. 25, 475-485 (1973; Zbl 0229.05129)] that every multigraph with \(e\) edges must contain a bipartite subgraph with at least \(\lceil e/2 + (\sqrt{8 e + 1} - 1)/8 \rceil\) edges. This paper provides a simpler proof for this result.
Recommendations
- The size of bipartite graphs with a given girth
- On the number of maximal bipartite subgraphs of a graph
- On a problem of a. kotzig concerning factorizations of 4‐regular graphs
- Sizes of graphs with induced subgraphs of large maximum degree
- scientific article; zbMATH DE number 4008428
- On the sizes of large subgraphs of the binomial random graph
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three
- The extremal number of the subdivisions of the complete bipartite graph
- The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
- Bipartite graphs of large clique-width
Cites work
Cited in
(30)- Towards the distribution of the size of a largest planar matching and largest planar subgraph in random bipartite graphs
- Bisections of graphs without \(K_{2, l}\)
- Judicious partitions of 3-uniform hypergraphs
- On bipartitions of directed graphs with small semidegree
- Maximum bisections of graphs without cycles of length 4
- Maximum bisections of graphs without short even cycles
- Max-bisections of \(H\)-free graphs
- Hypergraph cuts above the average
- Bipartite subgraphs
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- On k-partite subgraphs
- Long Local Searches for Maximal Bipartite Subgraphs
- Judicious partitions of directed graphs
- Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
- Bisections of graphs without short cycles
- Bisections of graphs
- scientific article; zbMATH DE number 840704 (Why is no real title available?)
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Maximum cuts in graphs without wheels
- Bipartite subgraphs of H-free graphs
- Maximum bipartite subgraphs in H-free graphs
- MAX-CUT BY EXCLUDING BIPARTITE SUBGRAPHS
- Graph partitioning: an updated survey
- Approximating sparse quadratic programs
- On bipartite restrictions of binary matroids
- Maximum bisections of graphs with girth at least six
- Maximum bisections of graphs without cycles of length four and five
- Factorization norms and an inverse theorem for MaxCut
- Proportional component order network connectivity
- On maximum bisections of \(\{C_4, \theta (2, 3, 3)\}\)-free graphs
This page was built for publication: The size of the largest bipartite subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377883)
