Open Problem Garden - Strong 5-cycle double cover conjecture - Comments

Indeed, no counterexamples (re: Strong 5-cycle double cover conjecture)

niekeaerts — Thu, 24 Nov 2011 17:54:48 +0100

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

Not a counterexample (re: Strong 5-cycle double cover conjecture)

Robert Samal — Thu, 24 Nov 2011 16:32:18 +0100

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

!!Ignore previous comment!! (re: Strong 5-cycle double cover conjecture)

niekeaerts — Wed, 23 Nov 2011 13:16:22 +0100

Sorry, I pressed reply at the wrong statement.

Explanation of the 3-connected counterexample (Part II) (re: Strong 5-cycle double cover conjecture)

niekeaerts — Wed, 23 Nov 2011 13:15:11 +0100

Now 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 towards and and therefore there will be no escape possibility from for the two new colors. So the triangle is colored with color 2. By symmetry the triangle is also one color cycle (color 4). Now , and are not colored and therefore need to be in the cycle of color 3 and the cycle of color 5. But then has degree 3 in both cycles which is a contradiction.
So a 5-cycle double cover containing this cycle does not exist.

Explanation of the 3-connected counterexample (re: Strong 5-cycle double cover conjecture)

niekeaerts — Wed, 23 Nov 2011 13:14:34 +0100

Consider the circuit 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 and are colored with the same color (color 2) in the second cycle covering them, and similarly and have the same color (color 3) in the second cycle covering them. (As otherwise is colored twice by the cycle which, if allowed, quickly shows necessity of 6 colors)

Consider the circuit to be (re: Strong 5-cycle double cover conjecture)

niekeaerts — Wed, 23 Nov 2011 13:10:09 +0100

Consider the circuit 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 and are colored with the same color (color 2) in the second cycle covering them, and similarly have the same color (color 3) in the second cycle covering them. (As otherwise is colored twice by the cycle which, if allowed, quickly shows necessity of 6 colors)

?: 3-connected Counterexample (re: Strong 5-cycle double cover conjecture)

niekeaerts — Wed, 23 Nov 2011 13:09:38 +0100

Adjacency matrix (in alphabetical order):

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

?: Counterexample for a graph with a 2-cut (re: Strong 5-cycle double cover conjecture)

niekeaerts — Wed, 23 Nov 2011 12:47:13 +0100

Adjacency matrix (in alphabetical order):

Consider the circuit 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

Strong 5-cycle double cover conjecture

arthur — Tue, 03 Aug 2010 13:55:30 +0200

Author(s): Arthur; Hoffmann-Ostenhof

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

Conjecture Let be a circuit in a bridgeless cubic graph . Then there is a five cycle double cover of such that is a subgraph of one of these five cycles.