Re: Four Color Theorem
- From: "bill" <b92057@xxxxxxxxx>
- Date: 1 Jul 2006 12:57:05 -0700
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?
What were the probable results?
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.
Think of it this way: If you take a pentagon and remove one vertex u,I am satisfied if the pentagon can always be properly 3-colored!
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.
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
.
- Follow-Ups:
- Re: Four Color Theorem
- From: Proginoskes
- Re: Four Color Theorem
- References:
- Re: Four Color Theorem
- From: bill
- Re: Four Color Theorem
- From: Proginoskes
- Re: Four Color Theorem
- Prev by Date: Re: Matrix exponantial problem; is there a good way?
- Next by Date: mathematica command for linearity
- Previous by thread: Re: Four Color Theorem
- Next by thread: Re: Four Color Theorem
- Index(es):
Relevant Pages
|
