Manhattan and Chebyshev flows

Titelangaben

Gáborik, Lukáš ; Kurz, Sascha ; Mazzuoccolo, Giuseppe ; Rajnik, Jozef ; Rieg, Florian:
Manhattan and Chebyshev flows.
Bayreuth , 2025 . - 25 S.
DOI: https://doi.org/10.15495/EPub_UBT_00008626

Volltext

Link zum Volltext (externe URL):

Abstract

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. 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 for the two norms 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.