Bounding Tree-Width via Contraction on the Projective Plane and Torus.
Bounding Tree-Width via Contraction on the Projective Plane and Torus.
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 …