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 covering every edge exactly twice. We study the counting version of this statement for cubic graphs, where we count circuit double covers --- collections of circuits (connected 2-regular subgraphs) covering every edge twice. We show that every 2-edge-connected 3-edge-colorable cubic graph on $n$ vertices has at least $2^{n/2-1}$ circuit double covers, matching our previously conjectured general lower bound. For every 3-edge-connected cubic graph with girth at least 16 we show a weaker exponential lower bound on circuit double covers. For both of these results we use the same system of linear equations used by OpenAI in their proof, however, we provide additional combinatorial interpretation. We characterize planarity of a cubic graph by solvability of this system of equations for arbitrary nowhere-zero $\mathbb Z_2^k$-flow. We give a condition on the flow that is equivalent to existence of a 5-cycle double cover.
A proof of the cycle double cover conjecture was recently announced, yielding an $8$-cycle double cover for every bridgeless graph. The stronger $5$-cycle double cover conjecture, which is still open, is equivalent to the statement that the edge set of every bridgeless claw-free cubic graph can be covered by at most fo...
The Berge conjecture [Proc. London Math. Soc., 1979] asserts that every bridgeless cubic graph can be covered by five perfect matchings. The 5-cycle double cover conjecture, proposed independently by Preissmann (1981) and Celmins (1984), asserts that every bridgeless graph admits five even subgraphs such that every edg...
Tutte's flow conjectures ask when a graph has a nowhere-zero flow with small integer values. We approach these questions through spanning-tree packing and an analytic minimization argument of Alon, Buci\'c, and Davies. For every integer $q\ge2$, we prove that $q$ edge-disjoint spanning trees suffice to realize every co...
We study Tur\'an problems for balanced even cycles in simple signed graphs, where signed subgraphs are considered up to switching. For every balanced bipartite signed graph, the signed and ordinary Tur\'an numbers differ by at most a factor of two. Our main structural results concern the underlying graphs that admit a...
We prove the 3-Decomposition Conjecture: every finite connected cubic loopless multigraph decomposes into a spanning tree, a 2-regular subgraph, and a matching. The proof rests on a new theorem on matching complements in subcubic graphs. Let H be a finite connected bridgeless simple graph of maximum degree three, and l...
The Erdos-Gyarfas conjecture states that every graph with minimum degree at least 3 contains a cycle whose length is a power of two. We prove by a SAT-based exhaustive search, certified by DRAT proofs, that every graph with minimum degree at least 3 on at most 23 vertices contains a cycle of length 4 or a cycle of leng...
D. García· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
