MAXIMUM CUTS IN GRAPHS WITHOUT WHEELS

For a graph G, let f(G) denote the maximum number of edges in a bipartite subgraph of G. Given a fixed graph H and a positive integer m, 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. Alon et al. ['Maximum cuts and judicious partitions in graphs without short cycles', J. Combin. Theory Ser. B 88 (2003), 329-346] conjectured that, for any fixed graph H, there exists an epsilon(H) > 0 such that f(m, H) >= m/2 + Omega(m(3/4+epsilon)). We show that, for any wheel graph W-2k of 2k spokes, there exists c(k) > 0 such that f(m, W-2k) >= m/2 + c(k)m(()(2k)(-1)/()(3k)(-1)) log m. In particular, we confirm the conjecture asymptotically for W-4 and give general lower bounds for W-2k(+1).