Hušek–Šámal's exponential circuit double cover conjecture

Less than 1 year old · traced to

Let GG be a 22-connected cubic graph on nn vertices. A circuit double cover (CiDC) is a finite family of connected 22-regular subgraphs of GG such that every edge belongs to exactly two members of the family.

Hušek–Šámal's conjecture. The graph GG has at least

2n/2−12^{n/2-1}

CiDCs.

This is a quantitative strengthening of the cycle double cover problem. The bound is proved in the source for 22-connected 33-edge-colorable cubic graphs and is known to be tight for Klee graphs, while the general conjecture remains open.

References

Primary source

Radek Hušek and Robert Šámal, “Exponentially Many Circuit Double Covers”, arXiv:2607.24724 (2026).

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.