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

  • Evan Morgan
  • Bogdan Oporowski
Keywords: Graph theory, Toroidal graphs, projective planar graphs, tree-width, series-parallel, contraction

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.
Published
2015-10-16
Article Number
P4.5