Article contents
BIPARTITE SUBGRAPHS OF $H$-FREE GRAPHS
Published online by Cambridge University Press: 07 February 2017
Abstract
For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. For an integer $m$ and for a fixed graph $H$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$ as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. We give a general lower bound for $f(m,H)$ which extends a result of Erdős and Lovász and we study this function for any bipartite graph $H$ with maximum degree at most $t\geq 2$ on one side.
MSC classification
- Type
- Research Article
- Information
- Copyright
- © 2017 Australian Mathematical Publishing Association Inc.
Footnotes
This work is supported by NSFC (Grant No. 11671087) and New Century Programming of Fujian Province (Grant No. JA14028).
References
- 10
- Cited by