Seminar of Graph Theory - Robert Lukoťka (11.12.2025)
Thursday 11.12.2025 at 9:50, Lecture room M 213
Robert Lukoťka:
Rich nowhere-zero flows on general graphs
Abstract:
A rich k-flow is a nowhere-zero k-flow such that each pair of neighbouring edges has different absolute flow values. We show the following. If a graph G with maximum degree Delta admits a rich k-flow for some k, then it admits a rich (264.Delta-521)-flow. The proof utilizes an idea from Seymour's proof of the 6-flow theorem. Besides this, we will discuss several variations of the notion of rich flow, focusing on complete bipartite and complete graphs.