The size of the largest bipartite subgraphs (Q1377883)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The size of the largest bipartite subgraphs |
scientific article; zbMATH DE number 1110120
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The size of the largest bipartite subgraphs |
scientific article; zbMATH DE number 1110120 |
Statements
The size of the largest bipartite subgraphs (English)
0 references
13 May 1998
0 references
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.
0 references
bipartite subgraph
0 references
0.91518813
0 references
0.91393113
0 references
0.91297364
0 references
0.9031247
0 references
0.9025097
0 references
0.90208536
0 references
0.9016373
0 references
0.90114164
0 references
0.89929193
0 references
