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

Evan Morgan, Bogdan Oporowski

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.

Keywords


Graph theory; Toroidal graphs; projective planar graphs; tree-width; series-parallel; contraction

Full Text: PDF