Alon–Tarsi–Jaeger short cycle cover conjecture
Alon–Tarsi–Jaeger short cycle cover conjecture
Let be a bridgeless graph with edges. A cycle cover of is a multiset of cycles from such that every edge of belongs to at least one cycle, and its length is the sum of the lengths of its cycles.
Short cycle cover conjecture. Every bridgeless graph with edges has a cycle cover of length at most .
This conjecture was independently proposed by Alon and Tarsi and by Jaeger. The paper proves weaker bounds for bridgeless cubic graphs, so the stated bound remains unresolved here.
Sources & referencesView supporting material
Primary source
Robert Lukoťka, “Short cycle covers of cubic graphs and intersecting 5-circuits”, arXiv:1901.10718 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.