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

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

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

07. 10. 2019 13.12 hod.
Od: Martin Škoviera

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

Názov: : Cubic graphs with no short cycle covers

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

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.