Seminar of Graph Theory - Martin Škoviera (7.11.2024)
Thursday 7.11.2024 at 9:50, Lecture room M 213
Martin Škoviera:
Short cycle covers of cubic graphs with colouring defect 3, and more
Abstrakc:
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.