Seminar of Graph Theory - Róbert Lukoťka (28.11.2019)

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

---

Róbert Lukoťka:
Circular flow number of cubic graphs in O(1.5^n) time

Abstract:
We show that the circular flow number of a cubic graph can be determined in time O(1.94^n). The running time can be improved to O(1.5^n) if we do not need to distinguish the circular flow number values between 5 and 6. Finally, we observe that it is possible to decide the flow number of a cubic graph in O(1.26^n) time. We discuss how the results transfer to circular colourings.

 

 

---