The size of the largest bipartite subgraphs
type: Item
instance of: scholarly article
title: The size of the largest bipartite subgraphs
zbMATH Open document ID: 0888.05035
DOI: 10.1016/S0012-365X(97)00004-6
author: András Gyárfás
author: Yoshiharu Kohayakawa
author: P. Erdős
published in: Discrete Mathematics
publication date: 1998-05-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1110120
zbMATH Keywords: bipartite subgraph
MaRDI profile type: Publication
Wikidata QID: Q105815733
cites work: Some Extremal Properties of Bipartite Subgraphs
cites work: Q3842665
cites work: On some extremal problems in graph theory
cites work: On coloring graphs to maximize the proportion of multicolored k-edges
full work available at URL: s0012-365x(97)00004-6
OpenAlex ID: W2002958365
Recommended article: The size of bipartite graphs with a given girth
Recommended article: On the number of maximal bipartite subgraphs of a graph
Recommended article: On a problem of a. kotzig concerning factorizations of 4‐regular graphs
Recommended article: Sizes of graphs with induced subgraphs of large maximum degree
Recommended article: Q3758861
Recommended article: On the sizes of large subgraphs of the binomial random graph
Recommended article: Largest bipartite subgraphs in triangle-free graphs with maximum degree three
Recommended article: The Extremal Number of the Subdivisions of the Complete Bipartite Graph
Recommended article: The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
Recommended article: Bipartite Graphs of Large Clique-Width
description: scientific article; zbMATH DE number 1110120