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

Seminár z teórie grafov - Edita Mačajová (5.10.2017)

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

03. 10. 2017 10.33 hod.
Od: Martin Škoviera

Prednášajúci: Edita Mačajová 

Názov: Nowhere-zero flows on signed eulerian graphs

Termín: 5.10.2017, 9:50 hod., M/213

We generalise the well-known fact about the existence of nowhere-zero 2-flows in Eulerian graphs by showing that every signed Eulerian graph which admits an integer nowhere-zero flow has a nowhere-zero 4-flow. We also describe signed Eulerian graphs with flow number 2, 3, and 4, as well as those that do not have an integer nowhere-zero flow. The most difficult part of the proof is to characterise signed Eulerian graphs whose flow number equals 3, which requires proving a decomposition theorem for unsigned 6-regular graphs of odd order. In turn, the proof of latter result calls for the use of signed graphs as a technical tool. Finally, we discuss the existence of nowhere-zero A-flows on signed Eulerian graphs for an arbitrary Abelian group A.

The talk is based on a joint work with Martin Skoviera.