Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.22234 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912670137974784 |
|---|---|
| author | Gáborik, Lukáš Kurz, Sascha Mazzuoccolo, Giuseppe Rajník, Jozef Rieg, Florian |
| author_facet | Gáborik, Lukáš Kurz, Sascha Mazzuoccolo, Giuseppe Rajník, Jozef Rieg, Florian |
| contents | We investigate multidimensional nowhere-zero flows of bridgeless graphs. By extending the established use of the Euclidean norm, this paper considers the Manhattan and Chebyshev norms, leading to the definition of the flow numbers $Φ_d^1(G)$ and $Φ_d^\infty(G)$, respectively. These flow numbers are always rational and in two dimensions, they distinguish between cubic graphs that are 3-edge-colourable and those that are not. We also prove that, for any bridgeless graph $G$, the two values $Φ^1_2(G)$ and $Φ^\infty_2(G)$ are the same. We give new upper and lower bounds and structural results, and we find connections with cycle covers. Finally, we introduce the idea of $t$-flow-pairs, which comes from a method used in Seymour's proof of the 6-flow theorem, and we propose new conjectures that could be stronger than Tutte's famous 5-flow conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22234 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Manhattan and Chebyshev flows Gáborik, Lukáš Kurz, Sascha Mazzuoccolo, Giuseppe Rajník, Jozef Rieg, Florian Combinatorics We investigate multidimensional nowhere-zero flows of bridgeless graphs. By extending the established use of the Euclidean norm, this paper considers the Manhattan and Chebyshev norms, leading to the definition of the flow numbers $Φ_d^1(G)$ and $Φ_d^\infty(G)$, respectively. These flow numbers are always rational and in two dimensions, they distinguish between cubic graphs that are 3-edge-colourable and those that are not. We also prove that, for any bridgeless graph $G$, the two values $Φ^1_2(G)$ and $Φ^\infty_2(G)$ are the same. We give new upper and lower bounds and structural results, and we find connections with cycle covers. Finally, we introduce the idea of $t$-flow-pairs, which comes from a method used in Seymour's proof of the 6-flow theorem, and we propose new conjectures that could be stronger than Tutte's famous 5-flow conjecture. |
| title | Manhattan and Chebyshev flows |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.22234 |