Course No.：216031Y
Period：10
Credits：0.5
Course Category：Lecture
Primary Coverage：
Talks 1 -2 Introduction of CDC conjecture
The Circuit Double Cover (CDC) Conjecture is considered as one of the most important open problems in graphs.
The conjecture states as follows: Every bridgeless graph has a family of circuits that covers every edge precisely twice.
The CDC conjecture has been considered as a “folklore” with possible origin due to Tutte as early as 1940’s. It also appears in articles by Szekeres (1973), Itai and Rodeh (1978), Seymour (1979).
In the first two lectures, we will discuss the structure of minimal counterexample to the conjecture, its relation with the 3-edge-coloring problem, and some other related circuit covering problems (relaxation or generalization).
Talk 3 Faithful circuit cover
Let {1,2} be a weight of G. A weight w is eulerian if the total weight ofàw: E(G) every cut is even. For an eulerian weight of G, can we find a family of circuits covering every edge e precisely w(e) times? This is a generalization of circuit double cover problem (constant 2 weight). A family of circuit satisfying the above description is called a faithful circuit cover of (G,w). Unfortunately, the faithful covering problem is not always true (the Petersen graph is a counterexample). However, the faithful covering problem serves as an inductive approach for the CDC conjecture.
Talk 4 Circuit chain and weight decomposition
Let (G,w) be an eulerian weighted graph. (G,w)=(G’,w’)+(G’’+w’’) is a weight decomposition of (G,w) if G’ and G’’ are subgraph of G and $w=w’+w’’. If both (G’,w’) and (G’’,w’’) have faithful covers, so does (G,w). Can we decompose (G,w) into a pair of such smaller faithful covering problems?
Talk 5 Strong CDC, circuit extension
Strong CDC conjecture: for a given circuit C of a bridgeless graph G, the graph G has a CDC that contains the given circuit C.
Definition. Let C be a circuit of G. Another circuit C’ is an extension of C if V(C) is contained in V(C’).
Extension of circuit serves as an approach of the Strong CDC problem.
References:
1 CQ Zhang, Circuit Double Covers of Graphs (lecturenotes)
2. CQ Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker (1997).
3. F. Jaeger, A survey of the cycle double cover conjecture, in Cycles in Graphs, (B. Alspach and C. Godsil, eds.), Ann. Discrete Math. 27 (1985) p. 1-12.
Author：Cunquan Zhang 
