Re: FOUR COLOR THEOREM

Musatov wrote

bill wrote:
The Heawood four-color graph is a 25-node planar graph that tangles
the Kempe chains in Kempe's algorithm and thus provides an example of
how Kempe's supposed proof of the four-color theorem fails.

The example present a coloring of the graph which experiences an
impasse with the coloring of
the 25th vertex. The impasse is due to the following situation:

V_25 is adjacent to;
V_1 which is Y
V_2 which is R
V_3 which is B
V_4 which is R and
V_5 which is G.

Suppose, that instead of trying to color v_25, we remove it and
install an edge between v_2 and v_4. A proper 4-coloring of gthe
resulting graph demands that v_2 and/or v_4 be recolored.

A recoloring of v_2 and/or v_4 will result in two cases;

1) The set of vertices v_1 thru v_5 is 3-colorable. Then the
complete graph, with v_25 will
be 4-colorable, or

2) The set of vertices v_1 thru v_5 is not 3-colorable.and the
impasse still exists. But there
are still two vertices with the same color. An edge can be
installed between these two
vertices and the prolem returns.

Let G be the graph with v_25 removed. In essence,

3) Any coloring of G that does not permit a 4-coloring of the
complete graph can be
confounded by a strategically placed edge
4) G can be recolored so as to negate the impact of such an edge
and still deny a
4-coloring to the complete graph..

The cycle of 3), 4), 3), etc. will continue indefinitely unless there
is a configuration
of G that permits a 4-coloring of the complete graph.

IMMHO, the recoloring of G will eventually lead to a proper 4-coloring
of the complete
graph.

regards, Bil J

Thank you
.

Relevant Pages

  • Re: A restricted case of graph coloring, is this a known problem?
    ... performs n^2 recoloring steps, then each recoloring step must be done ... is a state in the DFA where the inputs transition to different ... the coloring. ... That is if you have a hard to color graph of inputs, ...
    (comp.theory)
  • FOUR COLOR THEOREM
    ... The Heawood four-color graph is a 25-node planar graph that tangles ... The impasse is due to the following situation: ... the recoloring of G will eventually lead to a proper 4-coloring ...
    (sci.math)
  • Re: The Lazy Persons Guide to Proving the Four Color Theorem
    ... In fact, the 4CT is false if there is a graph G with Chi> 4, ... For every possible 4-coloring of, there can be no proper ... rest of G, or equivalently, if C is a coloring of G, then Chas four ... You assumed we can recolor just v_a; ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... that no minimal counterexample of the 4CT contains K4. ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... that no minimal counterexample of the 4CT contains K4. ...
    (sci.math)