The width of quadrangulations of the projective plane

DOI10.1002/JGT.22241MaRDI QIDQ4553729zbMATH OpenOpenAlexFDO

Authors L. Esperet, Matěj Stehlík

Publication date 31 October 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.07716

zbMATH Keywords

odd cyclesprojective planequadrangulations

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) General theory of linear incidence geometry and projective geometries (51A05)

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 $frac12,(1+sqrt8n-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 $frac12,(1+sqrt8n-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 $frac14(1+sqrt16n-15)$, which is a constant away from the optimal; we prove a lower bound of $sqrtn$. Finally, we show that $G$ has an odd cycle transversal of size at most $sqrt2Deltan$ inducing a single edge, where $Delta$ is the maximum degree. This last result partially answers a question of Nakamoto and Ozeki.

Recommendations

• Chromatic numbers of quadrangulations on closed surfaces
• Small odd cycles in 4-chromatic graphs
• Quadrangulations and 5-critical graphs on the projective plane
• Quadrangulations and 4-color-critical graphs
• Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces

Cited in

(6)

• A proof of a dodecahedron conjecture for distance sets
• Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\)
• Chromatic numbers of quadrangulations on closed surfaces
• Quadrangulations and 5-critical graphs on the projective plane
• Projective Reeds-Shepp car onS²with quadratic cost
• Schrijver graphs and projective quadrangulations

This page was built for publication: The width of quadrangulations of the projective plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4553729)