Seminár z teórie grafov - Lukáš Gáborik (9.4.2026)
vo štvrtok 9.4.2026 o 9:50 hod. v miestnosti M 213
Prednášajúci: Lukáš Gáborik
Názov prednášky: Constructing flows from flow-pairs
Termín: 9.4.2026, 9:50 hod., M 213
Abstrakt:
A nowhere-zero k-flow is a mapping of values ±1, ±2, . . . , ±(k − 1) to darts of a graph satisfying Kirchhoff’s law – the inflow is the same as the outflow – for every vertex of the graph. It is conjectured [Tutte, 1954] that each bridgeless graph has a nowhere-zero 5-flow.
Almost three decades later, Seymour [Seymour, 1981] made a general construction of nowhere-zero 6-flow from a 2-flow and a 3-flow. Although these two flows permit zeroes, no edge can have both of them equal to zero simultaneously. In a recent preprint [Gáborik et al., 2025], along with the introduction of two-dimensional Chebyshev nowhere-zero flows, the authors showed a similar construction of the nowhere-zero 5-flow from a 2-flow and a 4-flow. In addition to forbidding simultaneous zero values, the flow values (0, 1) and (0, −1) are also excluded. This structure is called a 1/2-flow-pair.
In this talk, we explore the properties of 1/2-flow-pairs. We prove their existence on snarks with oddness 2, and we also show that one can construct a rich nowhere-zero 7-flow from them. We also use a generalised version of the 1/2-flow-pair to investigate the Chebyshev flow number and to show that the 2-dimensional Chebyshev flow number of snarks can be arbitrarily small.