Seminar of Graph Theory - Robert Lukoťka (29.9.2022)
Thursday 29.9.2022 at 9:50, Lecture room M/213
Robert Lukoťka:
r-Balanced flows on graphs
Abstract:
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.