Back to Search Start Over

Sparse graphs are near-bipartite

Authors :
Cranston, Daniel W.
Yancey, Matthew P.
Publication Year :
2019
Publisher :
arXiv, 2019.

Abstract

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])|\ge -1$ for every $W\subseteq 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])|\ge -4$ for every $W\subseteq V(G)$, and $G$ contains no subgraph from some finite family $\mathcal{H}$. We also construct infinite families to show that both results are best possible in a very sharp sense.<br />Comment: 37 pages, 21 figures; incorporates reviewer feedback; to appear in SIAM J. Discrete Math

Details

Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....e580876c09ce5c9d0181ffa0bc045a67
Full Text :
https://doi.org/10.48550/arxiv.1903.12570