| Meno: | Lukáš |
|---|---|
| Priezvisko: | Gáborik |
| Názov: | New approaches to nowhere-zero flow problems |
| Vedúci: | Mgr. Jozef Rajník, PhD. |
| Rok: | 2026 |
| Kľúčové slová: | graph theory, flow, oddness, rich flow, lower bound, generalised Blanuša snarks, generator, multipole |
| Abstrakt: | A nowhere-zero k-flow is a mapping of values \pm 1, \pm 2, ... , \pm (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. Tutte 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 the first part of this thesis, we develop a generator of cubic multipoles with a better performance comparing to other known generators. The multipoles are of a great relevance in the nowhere-zero flow area. In the next part, 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. Then we find a lower bound on two-dimensional Chebyshev flow number depending on the order of a snark. We also use a generalised version of the 1/2-flow-pair to show that the two-dimensional Chebyshev flow number of snarks can be arbitrarily small, and to construct a Chebyshev flow on generalised Blanuša snarks. |
Súbory diplomovej práce:
| New_approaches_to_nowhere_zero_flow_problems.pdf |
| attachments.tgz |
Súbory prezentácie na obhajobe: