Home » Subject » Graph Theory » Basic G.T. » Cycles

Strong 5-cycle double cover conjecture

Importance: High ✭✭✭
Author(s): Arthur
Hoffmann-Ostenhof
Subject: Graph Theory
» Basic Graph Theory
» » Cycles
Keywords: cycle cover
Recomm. for undergrads: yes
Prize: 50 Euro
Posted by: arthur
on: August 3rd, 2010
Conjecture   Let $ C $ be a circuit in a bridgeless cubic graph $ G $. Then there is a five cycle double cover of $ G $ such that $ C $ is a subgraph of one of these five cycles.

A cycle in $ G $ is meant to be a $ 2 $-regular subgraph of $ G $ . A five cycle double cover of $ G $ is a set of five cycles of $ G $ such that every edge of $ G $ is contained in exactly two of these cycles.

This conjecture is a combination and thus strengthening of the $ 5 $-cycle double cover conjecture and the strong cycle double cover conjecture.

Related problems

Cycle double cover conjecture

Bibliography



* indicates original appearance(s) of problem.
add new comment

?: 3-connected Counterexample

On November 23rd, 2011 niekeaerts says:

$ |VG|=8 $
$ |EG|=12 $
$ VG=\{a,b,c,d,e,f,g,h\} $
Adjacency matrix (in alphabetical order): \[ \left( \begin{array}{llllllll } 0&1&1&0&0&0&0&1 & 1&0&1&1&0&0&0&0 & 1&1&0&0&1&0&0&0 & 0&1&0&0&1&1&0&0 & 0&0&1&1&0&0&1&0 & 0&0&0&1&0&0&1&1 & 0&0&0&0&1&1&0&1 & 1&0&0&0&0&1&1&0 \end{array}\right)\]

For the explanation, see the following comment. -----------

It could be so that I am making a mistake, if so, please explain my mistake to me.
I came to this point by simple trial and error.
I would like to upload a simple picture, but I seem to be a little lost on how to do this.

Nieke Aerts

reply

Not a counterexample

On November 24th, 2011 Robert Samal says:

Dear Nieke,

unfortunately, your graph is definitely not a counterexample. I could not follow your explanations, let me instead show, why your graph with the indicated cycle has the desired 5-CDC.

Your graph is planar, 2-edge-connected and the circuit C is a boundary of one of the faces. It turns out that for all such instances the conjecture is true: consider all face boundaries -- a collection of circuits. Now a proper 4-coloring of the dual graph splits the circuits into four cycles, the given circuit is contained in one of them. (The fifth cycle can be empty in this case.)

Think about it, and if you still believe you have a counterexample, post again. For now, I am not reading the other comments, as they prove something that turns out to be false :-).

Best wishes, Robert

reply

Indeed, no counterexamples

On November 24th, 2011 niekeaerts says:

Dear Robert,

Thanks for your reply.

I was thinking that the cycles have to be connected, which is obviously not true. So therefore my thought-to-be-counterexamples weren't correct. Thanks for the help! I wouldn't mind deleting all those comments, but I am not sure how to :)

Best, Nieke

reply

Explanation of the 3-connected counterexample

On November 23rd, 2011 niekeaerts says:

Consider the circuit $ a,b,d,f,h,a $ to be color 1. And assume there is a 5-cycle cover containing this circuit as one of the cycles. We distinguish the cycles by color.
Then $ (a,b) $ and $ (a,c) $ are colored with the same color (color 2) in the second cycle covering them, and similarly $ (a,b) $ and $ (a,h) $ have the same color (color 3) in the second cycle covering them. (As otherwise $ (a,c) $ is colored twice by the cycle $ (a,c,a) $ which, if allowed, quickly shows necessity of 6 colors)

reply

Explanation of the 3-connected counterexample (Part II)

On November 23rd, 2011 niekeaerts says:

Now $ (b,c) $ still needs to be covered twice, which cannot be done by 1 color as then again one needs 6 colors. One of the colors has to be color 2, otherwise this will leave $ b $ towards $ a $ and $ d $ and therefore there will be no escape possibility from $ b $ for the two new colors. So the triangle $ a,b,c $ is colored with color 2. By symmetry the triangle $ f,g,h $ is also one color cycle (color 4). Now $ (c,e) $, $ (d,e) $ and $ (e,g) $ are not colored and therefore need to be in the cycle of color 3 and the cycle of color 5. But then $ e $ has degree 3 in both cycles which is a contradiction.
So a 5-cycle double cover containing this cycle does not exist.

reply

?: Counterexample for a graph with a 2-cut

On November 23rd, 2011 niekeaerts says:

$ |VG|=8 $
$ |EG|=12 $
$ VG=\{a,b,c,d,e,f,g,h\} $
Adjacency matrix (in alphabetical order): \[ \left( \begin{array}{llllllll } 0&1&1&1&0&0&0&0 & 1&0&1&1&0&0&0&0 & 1&1&0&0&1&0&0&0 & 1&1&0&0&0&1&0&0 & 0&0&1&0&0&0&1&1 & 0&0&0&1&0&0&1&1 & 0&0&0&0&1&1&0&1 & 0&0&0&0&1&1&1&0 \end{array}\right)\]

Consider the circuit $ a,c,e,g,f,d,a $ to be color 1, now on either side of the 2-cut, we need three more colors, of which only one color can serve both (due to the 2-cut), so we need at least 6 colors (6 cycles).

-----------
It could be so that I am making a mistake, if so, please explain my mistake to me.
I came to this point by simple trial and error.
I would like to upload a simple picture, but I seem to be a little lost on how to do this.

Nieke Aerts

reply

Consider the circuit to be

On November 23rd, 2011 niekeaerts says:

Consider the circuit $ a,b,d,f,h,a $ to be color 1. And assume there is a 5-cycle cover containing this circuit as one of the cycles. We distinguish the cycles by color.
Then $ (a,b) $ and $ (a,c) $ are colored with the same color (color 2) in the second cycle covering them, and similarly $ (a,c),(a,h) $ have the same color (color 3) in the second cycle covering them. (As otherwise $ (a,c) $ is colored twice by the cycle $ (a,c,a) $ which, if allowed, quickly shows necessity of 6 colors)

reply

!!Ignore previous comment!!

On November 23rd, 2011 niekeaerts says:

Sorry, I pressed reply at the wrong statement.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.