Not a counterexample

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


Comments are limited to a maximum of 1000 characters.
More information about formatting options