Bounding Tree-Width via Contraction on the Projective Plane and Torus.
Open Access
- 16 October 2015
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (4) , P4.5
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
This publication has 4 references indexed in Scilit:
- Approximation algorithms via contraction decompositionCombinatorica, 2010
- Surfaces, Tree-Width, Clique-Minors, and PartitionsJournal of Combinatorial Theory, Series B, 2000
- Forbidden minors characterization of partial 3-treesDiscrete Mathematics, 1990
- On the Problem of Decomposing a Graph into n Connected FactorsJournal of the London Mathematical Society, 1961