Sparse graphs are near-bipartite
share
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|W|-2|E(G[W])|> -1 for every W⊆ V(G), and G contains no K_4 and no Moser spindle. We prove that a simple graph G is near-bipartite when 8|W|-5|E(G[W])|> -4 for every W⊆ V(G), and G contains no subgraph from some finite family H. We also construct infinite families to show that both results are best possible in a very sharp sense.
READ FULL TEXT