Orientations of $10$-Edge-Connected Planar Multigraphs and Applications
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914421051228160 |
|---|---|
| author | Cranston, Daniel W. Li, Jiaao Su, Bo Wang, Zhouningxin Wei, Chunyan |
| author_facet | Cranston, Daniel W. Li, Jiaao Su, Bo Wang, Zhouningxin Wei, Chunyan |
| contents | A graph is called strongly $\Z_{2k+1}$-connected if for each boundary function $β: V(G)\mapsto \Z_{2k+1}$ with $\sum_{v\in V(G)}β(v)\equiv 0\pmod{2k+1}$, there exists an orientation $D$ of $G$ such that $d_D^+(v) - d_D^-(v) \equiv β(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_24292 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Orientations of $10$-Edge-Connected Planar Multigraphs and Applications Cranston, Daniel W. Li, Jiaao Su, Bo Wang, Zhouningxin Wei, Chunyan Combinatorics A graph is called strongly $\Z_{2k+1}$-connected if for each boundary function $β: V(G)\mapsto \Z_{2k+1}$ with $\sum_{v\in V(G)}β(v)\equiv 0\pmod{2k+1}$, there exists an orientation $D$ of $G$ such that $d_D^+(v) - d_D^-(v) \equiv β(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. |
| title | Orientations of $10$-Edge-Connected Planar Multigraphs and Applications |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.24292 |