SPARSE GRAPHS ARE NEAR-BIPARTITE

A multigraph G is near-bipartite if V(G) can be partitioned as I, F such that I is an independent set and F induces a forest. We prove that a multigraph G is near-bipartite when 3 vertical bar W vertical bar - 2 vertical bar E(G[W])vertical bar >= -1 for every W subset of V(G), and G contains no K-4 and no Moser spindle. We prove that a simple graph G is near-bipartite when 8 vertical bar W vertical bar - 5 vertical bar E(G[W])vertical bar >= -4 for every W subset of V(G), and G contains no subgraph from some finite family H. We also construct infinite families to show that both results are the best possible in a very sharp sense.