Workshop on the Cycle Double Cover Conjecture
- Start Date: 08/22/2007
- End Date: 08/31/2007
University of British Columbia
The Cycle Double Cover Conjecture (CDC) was proposed independently by
P.D. Seymour (1979) and G. Szekeres (1973). The conjecture is easy to state:
"For finite every 2-connected graph, there is a list of cycles (polygons)
such that every edge of the graph is an edge of exactly two cycles
in the list."
As an example, if the graph is embedded in a surface (without crossing
edges) in such a way that all faces are bounded by cycles,
then the boundary cycles of the faces will "double cover" the edges.
Although the statement of the conjecture is very simple, the solution
has eluded dozens of attacks over 30 years.
This conjecture (and its numerous variants) is considered by most graph
theorists to be one of the major open questions in the field.
One reason for this is the close connections that this problem has
with topological graph theory, the theory of Nowhere-zero flows,
graph colouring and polyhedral combinatorics. MathSciNet lists more
25 articles with "cycle double cover" (or "double cycle cover") in
the title.
The workshop will include some formal presentations
with the purpose of bringing the participants up to date on
techniques and recent results. Long collaborative working periods will
take the majority of the working time.
