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

Seminár z teórie grafov - Martin Škoviera (7.11.2024)

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


05. 11. 2024 21.10 hod.
Od: Martin Škoviera

Prednášajúci: Martin Škoviera

Názov: Short cycle covers of cubic graphs with colouring defect 3, and more

Termín: 7.11.2024, 9:50 hod., M 213


Abstrakt:
The shortest cycle cover conjecture (Alon & Tarsi; Jaeger; 1985) suggests that every bridgeless graph can have its edges covered with cycles of total length at most 7/5.m, where m is the number of edges. After almost 40 years, the 7/5-conjecture remains widely open. In this talk will discuss the current status of the conjecture and explain its links to other problems in the area. We also present results that imply the validity of the conjecture in two special cases. We show that the 7/5-conjecture holds (1) for cubic graphs that are three edges short of being coverable with three perfect matchings, and (2) for cubic graphs containing a pentagon with an edge whose removal together with endvertices leaves a 3-edge-colourable graph. This is a joint work with Jan Karabas, Edita Macajova, and Roman Nedela.

Stránka seminára