Orientations of $10$-Edge-Connected Planar Multigraphs and Applications

Abstract

A graph is called strongly ${\mathbb{Z}}_{2k+1}$-connected if for each boundary function ${\hat{I}}^2:V(G)\mapsto {\mathbb{Z}}_{2k+1}$ with ${\sum }_{v\in V(G)}{\hat{I}}^2(v)\equiv 0(\mathrm{mod}2k+1)$, there exists an orientation $D$ of $G$ such that $d_D^{+}(v)-d_D^{-}(v)\equiv {\hat{I}}^2(v)(\mathrm{mod}2k+1)$ for each $v\in V(G)$. We show that every planar multigraph with $5$ edge-disjoint spanning trees is strongly ${\mathbb{Z}}_5$-connected. This verifies a special case of the Additive Base Conjecture when restricted to planar graphs. Hence, every $10$-edge-connected directed planar graph admits an antisymmetric ${\mathbb{Z}}_5$-flow. So, by duality, every orientation of a planar graph of girth at least $10$ admits a homomorphism to a $5$-vertex tournament. Our result also gives a new proof of the known result that every planar graph of girth at least $10$ has a homomorphism to the $5$-cycle.