Alon–Tarsi–Jaeger short cycle cover conjecture

Let GG be a bridgeless graph with mm edges. A cycle cover of GG is a multiset of cycles from GG such that every edge of GG 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 mm edges has a cycle cover of length at most 1.4m1.4m.

This conjecture was independently proposed by Alon and Tarsi and by Jaeger. The paper proves weaker bounds for bridgeless cubic graphs, so the stated 1.4m1.4m 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.