Bounding Tree-Width via Contraction on the Projective Plane and Torus.

Abstract

If $X$ is a collection of edges in a graph $G$, let $G/X$ denote the contraction of $X$. Following a question of Oxley and a conjecture of Oporowski, we prove that every projective planar graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three. We prove that every toroidal graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three and four, respectively.