Alon–Tarsi shortest cycle cover conjecture for bridgeless graphs

Let GG be a bridgeless graph, and let a circuit cover be a family of circuits covering every edge of GG. Its length is the sum of the numbers of edges in its circuits. Alon–Tarsi conjecture. Every bridgeless graph GG has a circuit cover with length at most

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

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

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.