Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

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

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

27. 09. 2022 21.12 hod.
Od: Martin Škoviera

Prednášajúci: Robert Lukoťka

Názov: r-Balanced flows on graphs

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

An r-balanced flow is an assignment b of values to the vertices of G, an orientation O, and an assignment \phi of values to the edges of G such that 1. b(v) = deg(v) (mod 2), for each vertex v, 2. 0 <= \phi(e) <= (r-2)/r, for each edge e, 3. \sum_{e \in O^+} \phi(e) - \sum_{e \in O^-} \phi(e) = b(v), for each vertex v.

We show that this concept coincides with the concept of balanced valuations introduced by Jaeger and thus it coincides with circular nowhere-zero r-flows. This definition gives a practical approach to compute the circular flow number for graphs on up to approximately $100$ vertices using the state of the art ILP solvers. We discuss how similar ideas could be used for the dual concept of circular colourings of certain graphs.

Stránka seminára