On the minimum degree forcing \(F\)-free graphs to be (nearly) bipartite (Q932657): Difference between revisions

Let \(\beta(G)\) denote the minimum number of edges that can be deleted from \(G\) that results in a bipartite graph, and for a \(3\)-chromatic graph define \(\xi(F)\) to be the maximum \(k\) such that \(F\) can be homomorphically mapped into \(C_k\) for \(k\) odd. This is denoted by \(F \rightarrow C_k\). It is shown that for every \(\alpha, \eta > 0\), there exists an \(n_0\) such that if for every \(F\)-free \(G\), where \(F\) is \(3\)-chromatic, \(G\) has at least \(n_0\) vertices, and \(\delta (G) \geq \left\lfloor (2n)/(\xi(F) + 2) \right\rfloor + \eta n\), then \(\beta(G) \leq \alpha(n^2)\). It is also shown that for every \(\alpha > 0\), there is an \(\overline{\eta}> 0\) and an \(\overline{n}_0\) such that every \(F\)-free graph \(G\) of order \(n \geq \overline{n}_0\) and \(\delta (G) \geq \left\lfloor (2n)/(\xi(F) + 2) \right\rfloor - \overline{\eta} n\) contains a subgraph \(G'\) with at least \(e(G) - \alpha n^2\) edges such that \(G' \rightarrow C_{\xi(F) + 2}\).