Alon and Tarsi's shortest circuit cover conjecture

About 10 years old · traced to

Let GG be a 2-edge-connected cubic graph. A shortest circuit cover of GG is a circuit cover having minimum total length, denoted by scc⁡(G)\operatorname{scc}(G). Alon and Tarsi's conjecture. Every 2-edge-connected cubic graph has a shortest circuit cover with length at most

7∣E(G)∣5.\frac{7|E(G)|}{5}.

The conjecture improves the general 5∣E(G)∣/35|E(G)|/3 bound for 2-edge-connected graphs and would give a sharp universal bound for cubic graphs. It is also known as the Shortest Circuit Cover Conjecture and, as noted in the source, implies the Circuit Double Cover Conjecture.

References

Primary source

Yezhou Wu and Dong Ye, “Circuit Covers of Cubic Signed Graphs”, arXiv:1609.03620 (2016).

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.