The width of quadrangulations of the projective plane

Abstract

We show that every $4$-chromatic graph on $n$ vertices, with no two vertex-disjoint odd cycles, has an odd cycle of length at most $\frac{1}{2}(1+\sqrt{8n-7})$. Let $G$ be a non-bipartite quadrangulation of the projective plane on $n$ vertices. Our result immediately implies that $G$ has edge-width at most $\frac{1}{2}(1+\sqrt{8n-7})$, which is sharp for infinitely many values of $n$. We also show that $G$ has face-width (equivalently, contains an odd cycle transversal of cardinality) at most $\frac{1}{4}(1+\sqrt{16n-15})$, which is a constant away from the optimal; we prove a lower bound of $\sqrt{n}$. Finally, we show that $G$ has an odd cycle transversal of size at most $\sqrt{2\Delta n}$ inducing a single edge, where $\Delta$ is the maximum degree. This last result partially answers a question of Nakamoto and Ozeki.

15 pages, 4 figures (revised version)

References in corpus (1)

• Colouring quadrangulations of projective spaces

Cited by in corpus (1)

• Smallest $C_{2l+1}$-critical graphs of odd-girth $2k+1$