Seminar of Graph Theory - Robert Lukoťka (10.10.2017)

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

---

RNDr. Robert Lukoťka, PhD.:
Short cycle covers in cubic graphs and 5-cycles

Abstract:
A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph on m edges has a cycle cover of total length less than 1.571m. If the graph has no non-trivial 3-edge-cuts, then a cycle cover of total length less than 1.567m exists.

---