Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Edita Mačajová (10.10.2019)

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

07. 10. 2019 13.16 hod.
By: Martin Škoviera

Edita Mačajová:
Cubic graphs with no short cycle covers

The shortest cycle cover conjecture suggests that every bridgeless cubic can have its edges covered with a collection of cycles of total length not exceeding (7/5).m where m is the number of edges. The covering ratio 7/5 is best possible, being reached by the Petersen graph. However, all cyclically 4-connected cubic graphs where the length of a shortest cycle cover is known have covering ratio close to the natural lower bound which equals 4/3. In line with this observation, Brinkmannn et al. (JCTB, 2013) made a conjecture that every cyclically 4-connected cubic graph has a cycle cover of length at most (4/3)m+o(m). We disprove this conjecture by exhibiting an infinite family of cyclically 4-connected cubic graphs whose shortest cycle cover has length at least (4/3 + 1/69)m.