4 papers · 1 filter
Exponentially Many Circuit Double Covers
Radek Hušek, Robert Šámal
The cycle double cover conjecture of Szekeres and Seymour, the proof of which was recently announced by OpenAI, states that every bridgeless graph has a collection of cycles coveri…
Facial diagrams and cycle double cover
Babak Ghanbari, Robert Šámal
We approach the cycle double cover conjecture by looking for a circular 2-cell embedding of cubic graphs on an arbitrary surface. It is easy to see that if such an embedding exists…
Approximate cycle double cover
Babak Ghanbari, Robert Šámal
The Cycle double cover (CDC) conjecture states that for every bridgeless graph , there exists a family of cycles such that each edge of the graph is contained in e…
Counting Circuit Double Covers
Radek Hušek, Robert Šámal
We study a counting version of Cycle Double Cover Conjecture. We discuss why it is more interesting to count circuits (i.e., graphs isomorphic to for some ) instead of cyc…