Seminár z teórie grafov - Robert Lukoťka (7.10.2021)

vo štvrtok 7.10.2021 o 9:50 hod. v miestnosti M/213

05. 10. 2021 14.32 hod.
Od: Martin Škoviera

Prednášajúci: Robert Lukoťka

Názov: Circular flow number of Goldberg snarks

Termín: 7.10.2021, 9:50 hod., M 213

A circular nowhere-zero r-flow on a bridgeless graph G is an orientation of the edges and an assignment of real values from [1, r-1] to the edges in such a way that the sum of incoming values equals the sum of outgoing values for every vertex. The circular flow number of G is the infimum over all values $r$ such that $G$ admits a nowhere-zero $r$-flow. We prove that the circular flow number of Goldberg snark G_{2k+1} is 4+1/(k+1), proving a conjecture of Goedgebeur, Mattiolo, and Mazzuoccolo [J.~Goedgebeur, D.~Mattiolo, G.~Mazzuoccolo: \emph{Computational results and new bounds for the circular flow number of snarks}, Discrete Mathematics 343 (2020), 112026.].

Besides this, we discuss computational aspects of circular flows. We describe an efficient way how to reformulate the problem of determining the circular flow number as a mixed linear programing problem. We review computational results obtained by this approach.

Stránka seminára