Seminar of Graph Theory - Lukáš Gáborik (10.10.2024)
Thursday 10.10.2024 at 9:50, Lecture room M 213
Lukáš Gáborík:
Chebyshev and Manhattan nowhere-zero flows
Abstract:
The area of nowhere-zero flows has been widely researched since its introduction by Tutte in 1954, when he also conjectured that each bridgeless graph has a nowhere-zero 5-flow. Recently, Mattiolo et al. researched real-valued nowhere-zero flows in two dimensions. They found some interesting properties (as rationality), in which 1D and 2D flows differ. We examine whether one can achieve better consistency by changing the considered norm from the Euclidean to the Chebyshev or the Manhattan one. In the two-dimensional case, we prove a one-to-one correspondence between Chebyshev and Manhattan flows, characterise graphs with unit vector flows and find some bounds on the flow number. Moreover, we observe a structure whose existence implies a 1D 5-flow and a 2D 2.5-flow, which opens a new possible way to prove Tutte's 5-flow conjecture. This is joint work with Sascha Kurz, Giuseppe Mazzuoccolo, Jozef Rajník, Florian Rieg and Gloria Tabarelli.