Alon and Tarsi's shortest circuit cover conjecture
Let be a 2-edge-connected cubic graph. A shortest circuit cover of is a circuit cover having minimum total length, denoted by . Alon and Tarsi's conjecture. Every 2-edge-connected cubic graph has a shortest circuit cover with length at most
The conjecture improves the general 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
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.