The width of quadrangulations of the projective plane

Louis Esperet, Matěj Stehlík

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-bip…