2 results
MAX-CUT BY EXCLUDING BIPARTITE SUBGRAPHS
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 108 / Issue 2 / October 2023
- Published online by Cambridge University Press:
- 08 November 2022, pp. 177-186
- Print publication:
- October 2023
-
- Article
-
- You have access
- HTML
- Export citation
-
For a graph G, let
$f(G)$ denote the maximum number of edges in a bipartite subgraph of G. Given a positive integer m and 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 prove bounds on 
$f(m,H)$ for some bipartite graphs H and give a bound for a conjecture of Alon et al. [‘MaxCut in H-free graphs’, Combin. Probab. Comput. 14 (2005), 629–647] concerning 
$f(m,K_{4,s})$.
BIPARTITE SUBGRAPHS OF
$H$-FREE GRAPHS
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 96 / Issue 1 / August 2017
- Published online by Cambridge University Press:
- 07 February 2017, pp. 1-13
- Print publication:
- August 2017
-
- Article
-
- You have access
- Export citation
-
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.
