Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Radek Hušek (23.11.2017)

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


20. 11. 2017 09.56 hod.
By: Martin Škoviera

Radek Hušek (Charles University, Prague):
On two flow problems


Abstract:

I will cover two main topics. The first one is group connectivity -- namely proving that Z_4-connectivity does not imply Z_2^2-connectivity, which answers a question suggested by Jaeger et al. [Group connectivity of graphs – A nonhomogeneous analogue of nowhere-zero flow properties, JCTB 1992]. Our proof is computer aided but uses a nontrivial enumerative algorithm.

In the second part I will present our approach to the following conjecture of Matt DeVos: If there is a graph homomorphism from Cayley graph Cay(M, B) to another Cayley graph Cay(M', B') then every graph with (M, B)-flow has (M', B')-flow. This conjecture was originally motivated by the flow-tension duality. We show that a natural strengthening of this conjecture does not hold in all cases but we conjecture that it still holds for an interesting subclass of them and we prove a partial result in this direction. We also show that the original conjecture implies the existence of oriented cycle double cover with a small number of cycles.