Sparse graphs are near-bipartite

Daniel W. Cranston, Matthew P. Yancey

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-bipart…