Abstract:A graph is called strongly $\Z_{2k+1}$-connected if for each boundary function $\beta: V(G)\mapsto \Z_{2k+1}$ with $\sum_{v\in V(G)}\beta(v)\equiv 0\pmod{2k+1}$, there exists an orientation $D$ of $G$ such that $d_D^+(v) - d_D^-(v) \equiv \beta(v) \pmod{2k+1}$ for each $v \in V(G)$.
We show that every planar multigraph with $5$ edge-disjoint spanning trees is strongly $\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 $\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.
From: Bo Su [view email]
[v1]
Wed, 25 Mar 2026 13:29:13 UTC (449 KB)
[v2]
Sun, 16 Aug 2026 13:48:41 UTC (453 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。