How to make a graph bipartite

The following theorems are proved: (1) Every triangle-free graph with n vertices and \(m\) edges can be made bipartite by the omission of at most \(\min \{(m/2)-2m(2m^2-n^3)/[n^2(n^2-2m)],m-4m^2/n^2\}\) edges. (2) There exists a constant \(\epsilon >0\) such that every triangle-free graph with \(n\) vertices can be made bipartite by the omission of at most \((1/18-\epsilon +o(1))n^2\) edges. (3) For every forbidden graph \(F\) and for every \(c>0\) there exists a constant \(\epsilon =\epsilon (F,c)>0\) such that any \(F\)-free graph with \(n\) vertices and \(m\geq cn^2\) edges can be made bipartite by the omission of at most \(m/2-\epsilon n^2\) edges. (4) If \(f=f(n,m)\) is the maximum integer such that every triangle-free graph with n vertices and at least \(m\) edges contains an induced bipartite subgraph with at least \(f\) edges then (i) \((1/2)m^{1/3}-1\leq f(n,m)\leq cm^{1/3}\log^2m\) if \(m<n^{3/2},\) (ii) \(4m^2/n^4\leq f(n,m)\leq c(m^3/n^4)\log^2(n^2/m)\) if \(m\geq n^{3/2}\). Several related questions, generalizations and unsolved problems are also considered.

Recommendations

Cited in

(38)

This page was built for publication: How to make a graph bipartite

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805628)