Seminar of Graph Theory - Edita Mačajová (4.12.2025)
Thursday 4.12.2025 at 9:50, Lecture room M 213
Edita Mačajová:
Rich nowhere-zero flows
Abstract:
A graph admits a nowhere-zero k-flow if its edges can be oriented and assigned values the set {1, 2, ..., k-1} in such a way that, at every vertex, the sum of the incoming values equals the sum of the outgoing values. The concept of a nowhere-zero flow is one of the most important concepts in graph theory and has been studied for more than half a century. In this talk, we introduce -- for cubic graphs -- the notion of a *rich* nowhere-zero k-flow: one where the three values at every vertex are pairwise distinct. We conjecture that a cubic graph admits a nowhere-zero k-flow if and only if it admits a rich nowhere-zero (k+1)-flow. We prove this conjecture for k=3 and k=4, that is, for bipartite and 3-edge-colourable cubic graphs, respectively. Furthermore, we show that every bridgeless cubic graph admits a rich nowhere-zero 11-flow and conjecture that 6 in place of 11 will do.
This is a joint work with Karolína Pisoňová.