
doi: 10.1007/bf01261315
\(f(G)\) denotes the maximum number of edges in a bipartite subgraph of any simple graph \(G\); \(f(e)\) dentoes the minimum of \(f(G)\) as \(G\) ranges over all graphs \(G\) having \(e\) edges. Erdös has conjectured that \(\limsup_{e\to\infty} \Biggl(f(e)-{e\over 2}+{-1+\sqrt{8e+1}\over 8}\Biggr)=\infty\). Theorem 1.1. There exist a positive constant \(c\) and an integer \(n_0\) such that, for \(e={n^2\over 2}\), where \(n\) is any sufficiently large integer, \(f(e)\geq{e\over 2}+\sqrt{{e\over 8}}+ce^{{1\over 4}}\). It is observed that this result is ``tight'', in the sense that there exists a positive constant \(C\) such that, for every \(e\), \(f(e)\leq{e\over 2}+\sqrt{{e\over 8}}+Ce^{{1\over 4}}\). Theorem 1.2. There exists a positive constant \(c'\) such that, for every triangle-free graph \(G\) with \(e>1\) edges, \(f(G)\geq{e\over 2}+c'e^{{4\over 5}}\). This latter result is shown to be ``tight'' in the sense that there exists a positive constant \(C'\) such that, for every positive integer \(e\), there exists a triangle-free graph \(G\) having \(e\) edges, such that \(f(G)\leq{e\over 2}+C'e^{{4\over 5}}\). In a note added in proof the author observes that J. Shearer has independently shown earlier that, for any \(\varepsilon>0\), any triangle-free graph with \(e\) edges and sufficiently many vertices contains a bipartite subgraph with at least \({e\over 2}+\Omega(e^{{4\over 5}-\varepsilon})\) edges. There are misprints.
bipartite subgraph, Extremal problems in graph theory, Coloring of graphs and hypergraphs, triangle-free graph
bipartite subgraph, Extremal problems in graph theory, Coloring of graphs and hypergraphs, triangle-free graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 65 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
