Re: Four Color Theorem


Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Hypothesis: A simple loopless maximal planar graph with a 5-degree
vertex cannot be a
minimal counter example to the four color theorem!.

Actually, that should be a lemma, not a hypothesis.



In Message-ID: <1141801956.464981.70430@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>

Date: 7 Mar 2006 23:12:36 -0800. you stat;

"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."

But has anyone proved that a 5-degree vertex is NOT a reducible
configuration?


One way to make a 5-degree vertex into a reducible configuration is to prove that
you cannot force a 4-coloring on a 5-cycle graph. Has this been tried? If so,
why did the proof fail?

A few people have tried to say that since a 5-cycle can be colored with
3 colors, that leaves you with one color for the center vertex v.
(Someone posted a paper at LANL within the past couple of years with
this idea.) However, you may need more colors than needed, because the
3-coloring of the 5-cycle might not be compatible with any of the other
colorings of G-v.

If it not, then the 4CT is false. But has anybody tried to prove that you can't
force a 4-coloring on a 5-cycle graph?

Probably.

What were the probable results?

Think of it this way: If you take a pentagon and remove one vertex u,
then the neighbors of u can be colored the same. (There is no edge
between them.) But there is no way to 2-color the entire pentagon.

I am satisfied if the pentagon can always be properly 3-colored!

True, but the point of the example is: You can't just concentrate on
the neighborhood of a certain vertex; a coloring is a global object.

The same argument applies if "pentagon" is replaced by "a cycle of
length (2 * google plex + 3)". If you pick a single vertex v and look
at all the vertices within a distance of a google plex of v, you will
have a 2-colorable graph, yet the entire graph is not 2-colorable.



--- Christopher Heckman

.

Relevant Pages

  • Re: Four Color Theorem
    ... you cannot force a 4-coloring on a 5-cycle graph. ... colorings of G-v. ... then the neighbors of u can be colored the same. ... But there is no way to 2-color the entire pentagon. ...
    (sci.math)
  • Static code analysis
    ... calls to a given function on a lower layer ... browser info into a call graph, and make a query tool capable of analyzing ... depending on circumstances looked up in configuration tables). ... call through a base class pointer to the implementation in a derived class. ...
    (comp.lang.cpp)
  • Re: Four Color Theorem
    ... configuration. ... you cannot force a 4-coloring on a 5-cycle graph. ... then the neighbors of u can be colored the same. ... But there is no way to 2-color the entire pentagon. ...
    (sci.math)
  • Re: Transform Filter Run() not being called
    ... Certain configuration = narrowed down to use of a certain MPEG-2 decoder. ... The graph uses the FileSourceFilter, MainConcept MPEG Demuxer, one of two MPEG-2 decoders, my filter, and VMR9. ...
    (microsoft.public.win32.programmer.directx.video)
  • Re: Unable to Stop a graph
    ... >> filter graph and then render the graph? ... >playing MPEG-2 videos with the ULead decoder. ... >This could be related to some configuration on my machine because I ...
    (microsoft.public.win32.programmer.directx.video)