Alon–Tarsi shortest cycle cover conjecture for bridgeless graphs
Alon–Tarsi shortest cycle cover conjecture for bridgeless graphs
Let be a bridgeless graph, and let a circuit cover be a family of circuits covering every edge of . Its length is the sum of the numbers of edges in its circuits. Alon–Tarsi conjecture. Every bridgeless graph has a circuit cover with length at most
This is the Shortest Cycle Cover Conjecture, concerning the minimum total length of circuit covers of bridgeless graphs. The conjecture is presented as a well-known open problem in the source.
Sources & referencesView supporting material
Primary source
Yezhou Wu and Dong Ye, “Minimum T-Joins and Signed-Circuit Covering”, arXiv:1803.03696 (2018).
Additional references
4 papers in this index state this conjecture (2012–2018). The statement above is taken from the most recent of them; the others are arXiv:1706.03808, arXiv:1306.3088, arXiv:1209.4510.
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.