HackerPapers

arXiv:1202.0569cs.DM

A Constructive Proof of the Cycle Double Cover Conjecture

Alexander Souza

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

The cycle double cover conjecture states that a graph is bridge-free if and only if there is a family of edge-simple cycles such that each edge is contained in exactly two of them. It was formulated independently by Szekeres (1973) and Seymour (1979). In this paper, we settle the conjecture in the affirmative. In particular, we give an algorithm, which inductively constructs a cycle double cover in polynomial time.

arXiv comments
Due to a flaw in Lemma 9, the paper has been withdrawn
Journal reference
DOI
Subjects
cs.DMDiscrete Mathematics cs.DSData Structures and Algorithms math.COCombinatorics

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Feb 2012 to Feb 2012. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.