Seminar of Graph Theory - Robert Šámal (30.11.2017)

Thursday 30.11.2017 at 9:50, Lecture room M/213

28. 11. 2017 13.41 hod.
By: Martin Škoviera

Robert Šámal (Charles University, Prague):
3-Flows with Large Support

Abstract:
We prove that every 3-edge-connected graph has a 3-flow that takes on a zero value on at most one sixth of the edges. The graph $K_4$ demonstrates that this $1/6$ ratio is best possible; there is an infinite family where $1/6$ is tight. The proof involves interesting work with connectivity of the graph (relaxing to subdivisions of 2-edge-connected graphs and then reducing to cyclically 4-edge-connected ones). Joint work with M. DeVos, J. McDonald, I. Pivotto, and E. Rollova.