|
|
| Author |
Message |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
 Posted: Thu Jul 13, 2006 11:59 pm Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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!.
It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.
Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.
This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.
My proof is based on the assumption that the following graph is not 4-chroma.
[The drawing below is correct in the "print" mode}
If you're going to post plain text which is supposed to line up, use a
proportional font, like Courier.
|..............| Internal chord
|--------------| External {B-C-B} Kempe chain
D <== A-----B-----C-----B------D ==> A
|--------------|--------------| External {A-C) & {C-D}
Kempe chains
The graph is planar. The {B-C-B} chain may cross the {A-C} & {C-D} chains
at common 'C' vertices.
It looks like you made Kempe's mistake again.
The graph is an attempt to find a feasible method of forcing a 4-coloring on a
chordless 5-cycle graph, without adding any chords. Without the internal chord
It is supposed to be a graph that cannot be 3-colored! With the "internal" chord,
theoretically, it cannot be properly 4-colored..
Theoretically; but (as I've told you before), if you have a planar
graph with a face of size >= 4, then there is more than one coloring.
All you have done is made one coloring fail to work; you haven't done
anything to the rest, which may still work. (In fact, in the graph G
with a pentagon, there are at least 2^(5-3) = 8 colorings. I'm not sure
whether this counts permutation of the colors or not.)
[BTW , 2^(5-3) = 4 not 8]
|
My point still holds.
| Quote: | I still say that there is only one 4-coloriing of a pentagon.
|
That is true.
| Quote: | I have not made it fail. I jusr have not found the configuration that will
make it work.
Just for discussion, suppose you or I find a configuration that does work?
Then I add a couple of chords to maximize graph H. Graph H still has
fewer vertices than G. If H is not 4-colorable, then G is not an mce
because it is not minimum. One of the chords connects two vertices
with the same color. Unless one or more of the vertices of H can be
recolored, H is not properly 4-colorable. And if one or more vertices can
be recolored, then perhaps H can be properly 3-colored.
How can I make you understand what I am trying to do?
Essentially, a 4-coloring of the pentagon (P) is the only way to make graph H
4-colorable and graph G not 4-colorable! If P is 4-colorable, then two vertices
have the same color. If a chord is added between these two vertices, H will
still be smaller than G. This chord makes the colorability of H uncertain.
If P is 3-colorable, then G is 4-colorable!
If H is not 4-colorable, then G is not minimal!
If P is 4-colorable, but not 3-colorable; then and only then G is an mce!
|
The graph has to come before the coloring. Sure, if you have a coloring
C, you can find a graph for which C is not a proper coloring. But
that's not how the 4CT is worded.
--- Christopher Heckman
| Quote: | I expect that someone will reveal the flaw. Then I will observe that
you can't force a 4-coloring without at least 3 external chains and
that this is the only way to get three chains.
With only two chains, the colors of only three vertices may be "forced"
. [Each
vertex has only two neighbors. Therefore, there are at least two
color options
for each vertex. "Forcing" means removing all but one option!]
This leaves 2 vertices whose colors cannot be forced by chains; but by some
unknown configuration?
Before I go any further, does anyone care to comment on the 3-chain configuration?
Also, any suggestions as to how a specific vertex can be forced to be a specific
color?
Exactly what was "Kempe's mistake"?
See http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm . Two
graphs for which his proof fails are given by:
http://mathworld.wolfram.com/KittellGraph.html (23 vertices)
http://mathworld.wolfram.com/ErreraGraph.html (17 vertices)
I think that "Kempe's mistake" must have been that he could not prove
that his method could properly 3-color the cycle graph? I don't care
if
the cycle graph can be 3-colored or not!
regards
---Bill J.
--- Christopher Heckman |
|
|
| Back to top |
|
 |
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Fri Jul 14, 2006 12:47 am Post subject:
Re: Four Color Theorem
|
|
|
a.khanm@gmail.com wrote:
| Quote: | Quite true. But when I said "inductive argument" I had something
different in mind. For instance if there were a feasible way (a finite
set of rules) of generating any arbitrary triangulation on n vertices
say Tn inductively from a triangulation on n-1 vertices say Tn-1 then
four colour theorem could be proved inductively by extending the four
colouring of
Tn-1 to Tn.
In the past people have used two simple rules:
1. adding a vertex to an existing face of Tn-1 (i.e., adding a vertex
of degree 3)
2. adding a vertex to an existing edge Tn-1 (i.e., adding a vertex of
degree 4)
Clearly Tn obtained by any of these rules is reducible. However,
someone by the name of R.E. Kenyon Jr. has used the operation of
expanding an existing vertex of Tn-1 to generate all triangulations
inductively. See
http://www.xenodochy.org/article/fourcolor.html
|
The idea of induction is that the new vertex will be adjacent to only
three existing vertices; and therefore cannot increase the
colorability.
If the new vertex is adjacent to more than 3 other vertices how can
4-colorability be guaranteed?
| Quote: |
But this is quite trivial and takes us right back where we started.
Proginoskes wrote:
a.khanm@gmail.com 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!.
It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.
Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.
This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.
But a variation of induction is the backbone to reduction, a technique
that both Appel and Haken, and Robertson Sanders Seymour Thomas used to
find a proof.
--- Christopher Heckman |
|
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Fri Jul 14, 2006 12:55 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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!.
It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.
Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.
This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.
My proof is based on the assumption that the following graph is not 4-chroma.
[The drawing below is correct in the "print" mode}
If you're going to post plain text which is supposed to line up, use a
proportional font, like Courier.
Actually, that should be FIXED font.
But it lines up perfectly on my screen! Did you try the print mode?
I'm using Google Groups to post, and there is no "print mode"
available.
Did you find the "print" mode"? It's under "Options" as is "Remove".
Yes. But relying on "print" mode is still bad practice for Usenet.
In a fixed font, the following would appear as a straight (dashed)
line, with 'ABC' under it:
\
\
\
\
\
\
\
ABC \
If the line appears broken, then you're not using the Usenet standard.
|..............| Internal chord
|--------------| External {B-C-B} Kempe chain
D <== A-----B-----C-----B------D ==> A
|--------------|--------------| External {A-C) & {C-D}
Kempe chains
That one came out okay.
The graph is planar. The {B-C-B} chain may cross the {A-C} & {C-D} chains
at common 'C' vertices.
So? What about the other vertices in the graph G?
If the graph above is 4-Chroma, then the other vertices in G are irrelevant.
If its not, the the other vertices in G cannot make it 4-chroma. At least that is
my contention.
But a coloring is a global object, not a local one. Consider the
analogy of a graph which is a cycle of length 2*10^100 + 3 and choose a
vertex v. If you look at all the vertices within a distance of 10^100
from v, you will get a graph that only needs 2 colors. But the overall
graph needs 3 colors.
So what! This has nothing to do with my need to make the cycle not |
3-colorable!
regards
---Bill J
| Quote: |
It looks like you made Kempe's mistake again.
Maybe not ... (See the note below.)
What is Kempe's mistake? When did I make it before?
BTW; you suggested the B-C-B chain idea!
I'm keeping half an eye out on a few dozen threads in four math
newsgroups. You'll have to be more specific than that.
--- Christopher Heckman |
|
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Fri Jul 14, 2006 2:10 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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!.
It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.
Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.
This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.
My proof is based on the assumption that the following graph is not 4-chroma.
[The drawing below is correct in the "print" mode}
If you're going to post plain text which is supposed to line up, use a
proportional font, like Courier.
|..............| Internal chord
|--------------| External {B-C-B} Kempe chain
D <== A-----B-----C-----B------D ==> A
|--------------|--------------| External {A-C) & {C-D}
Kempe chains
The graph is planar. The {B-C-B} chain may cross the {A-C} & {C-D} chains
at common 'C' vertices.
It looks like you made Kempe's mistake again.
The graph is an attempt to find a feasible method of forcing a 4-coloring on a
chordless 5-cycle graph, without adding any chords. Without the internal chord
It is supposed to be a graph that cannot be 3-colored! With the "internal" chord,
theoretically, it cannot be properly 4-colored..
Theoretically; but (as I've told you before), if you have a planar
graph with a face of size >= 4, then there is more than one coloring.
All you have done is made one coloring fail to work; you haven't done
anything to the rest, which may still work. (In fact, in the graph G
with a pentagon, there are at least 2^(5-3) = 8 colorings. I'm not sure
whether this counts permutation of the colors or not.)
[BTW , 2^(5-3) = 4 not 8]
My point still holds.
|
A 3-coloring of the pentagon (P) does not work because G would be
4-colorable. A 5-coloring of P does not work because H would not be
4-colorable. If there is only one 4-coloring, all the others must be
3-colorings or 5-colorings, which inherently don't work!
| Quote: |
I still say that there is only one 4-coloring of a pentagon.
That is true.
I have not made it fail. I jusr have not found the configuration that will
make it work.
Just for discussion, suppose you or I find a configuration that does work?
Then I add a couple of chords to maximize graph H. Graph H still has
fewer vertices than G. If H is not 4-colorable, then G is not an mce
because it is not minimum. One of the chords connects two vertices
with the same color. Unless one or more of the vertices of H can be
recolored, H is not properly 4-colorable. And if one or more vertices can
be recolored, then perhaps H can be properly 3-colored.
How can I make you understand what I am trying to do?
Essentially, a 4-coloring of the pentagon (P) is the only way to make graph H
4-colorable and graph G not 4-colorable! If P is 4-colorable, then two vertices
have the same color. If a chord is added between these two vertices, H will
still be smaller than G. This chord makes the colorability of H uncertain.
If P is 3-colorable, then G is 4-colorable!
If H is not 4-colorable, then G is not minimal!
If P is 4-colorable, but not 3-colorable; then and only then G is an mce!
The graph has to come before the coloring. Sure, if you have a coloring
C, you can find a graph for which C is not a proper coloring. But
that's not how the 4CT is worded.
|
Can you explain the above observation in the context of the mce/4CT?
regards
---Bill J
| Quote: | --- Christopher Heckman
I expect that someone will reveal the flaw. Then I will observe that
you can't force a 4-coloring without at least 3 external chains and
that this is the only way to get three chains.
With only two chains, the colors of only three vertices may be "forced"
. [Each
vertex has only two neighbors. Therefore, there are at least two
color options
for each vertex. "Forcing" means removing all but one option!]
This leaves 2 vertices whose colors cannot be forced by chains; but by some
unknown configuration?
Before I go any further, does anyone care to comment on the 3-chain configuration?
Also, any suggestions as to how a specific vertex can be forced to be a specific
color?
Exactly what was "Kempe's mistake"?
See http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm . Two
graphs for which his proof fails are given by:
http://mathworld.wolfram.com/KittellGraph.html (23 vertices)
http://mathworld.wolfram.com/ErreraGraph.html (17 vertices)
I think that "Kempe's mistake" must have been that he could not prove
that his method could properly 3-color the cycle graph? I don't care
if
the cycle graph can be 3-colored or not!
regards
---Bill J.
--- Christopher Heckman |
|
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Fri Jul 14, 2006 4:39 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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!.
It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.
Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.
This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.
My proof is based on the assumption that the following graph is not 4-chroma.
[The drawing below is correct in the "print" mode}
If you're going to post plain text which is supposed to line up, use a
proportional font, like Courier.
|..............| Internal chord
|--------------| External {B-C-B} Kempe chain
D <== A-----B-----C-----B------D ==> A
|--------------|--------------| External {A-C) & {C-D}
Kempe chains
The graph is planar. The {B-C-B} chain may cross the {A-C} & {C-D} chains
at common 'C' vertices.
It looks like you made Kempe's mistake again.
The graph is an attempt to find a feasible method of forcing a 4-coloring on a
chordless 5-cycle graph, without adding any chords. Without the internal chord
It is supposed to be a graph that cannot be 3-colored! With the "internal" chord,
theoretically, it cannot be properly 4-colored..
Theoretically; but (as I've told you before), if you have a planar
graph with a face of size >= 4, then there is more than one coloring.
All you have done is made one coloring fail to work; you haven't done
anything to the rest, which may still work. (In fact, in the graph G
with a pentagon, there are at least 2^(5-3) = 8 colorings. I'm not sure
whether this counts permutation of the colors or not.)
[BTW , 2^(5-3) = 4 not 8]
My point still holds.
A 3-coloring of the pentagon (P) does not work because G would be
4-colorable. A 5-coloring of P does not work because H would not be
4-colorable. If there is only one 4-coloring, all the others must be
3-colorings or 5-colorings, which inherently don't work!
|
Nice speech, but it also shows that you aren't on topic here. (Later
on, I do agree that in a minimal counterexample, the pentagon P will be
4-colored, and there's only one way to do that, up to isomorphism and
changing colors.)
The point is: You can't assume there is only one coloring of G-v.
You get a coloring C from the minimality of G, and show that there is a
graph H where the coloring C doesn't work. However, there _are_ other
colorings of G-v which are proper for H.
| Quote: | I still say that there is only one 4-coloring of a pentagon.
That is true.
I have not made it fail. I jusr have not found the configuration that will
make it work.
Just for discussion, suppose you or I find a configuration that does work?
Then I add a couple of chords to maximize graph H. Graph H still has
fewer vertices than G. If H is not 4-colorable, then G is not an mce
because it is not minimum. One of the chords connects two vertices
with the same color. Unless one or more of the vertices of H can be
recolored, H is not properly 4-colorable. And if one or more vertices can
be recolored, then perhaps H can be properly 3-colored.
How can I make you understand what I am trying to do?
Essentially, a 4-coloring of the pentagon (P) is the only way to make graph H
4-colorable and graph G not 4-colorable! If P is 4-colorable, then two vertices
have the same color. If a chord is added between these two vertices, H will
still be smaller than G. This chord makes the colorability of H uncertain.
If P is 3-colorable, then G is 4-colorable!
If H is not 4-colorable, then G is not minimal!
If P is 4-colorable, but not 3-colorable; then and only then G is an mce!
The graph has to come before the coloring. Sure, if you have a coloring
C, you can find a graph for which C is not a proper coloring. But
that's not how the 4CT is worded.
Can you explain the above observation in the context of the mce/4CT?
|
Imagine you have a machine M which takes, as input, a planar graph G,
and produces a 4-coloring of G as output. (If one exists.) The 4CT
simply states that for every input, there is (at least) one output;
that is, you cannot find a planar graph G that causes M to "crash".
A minimal counterexample is a graph G which crashes M, but at the same
time, M will produce an output for any graph with fewer vertices than
G.
You are taking the output of a graph G-v and coming up with a new graph
H. The output from G-v does not work for H, but that does not imply
that the machine will crash with H as an input. So you don't have your
contradiction that proves the 4CT yet.
--- Christopher Heckman
| Quote: | I expect that someone will reveal the flaw. Then I will observe that
you can't force a 4-coloring without at least 3 external chains and
that this is the only way to get three chains.
With only two chains, the colors of only three vertices may be "forced"
. [Each
vertex has only two neighbors. Therefore, there are at least two
color options
for each vertex. "Forcing" means removing all but one option!]
This leaves 2 vertices whose colors cannot be forced by chains; but by some
unknown configuration?
Before I go any further, does anyone care to comment on the 3-chain configuration?
Also, any suggestions as to how a specific vertex can be forced to be a specific
color?
Exactly what was "Kempe's mistake"?
See http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm . Two
graphs for which his proof fails are given by:
http://mathworld.wolfram.com/KittellGraph.html (23 vertices)
http://mathworld.wolfram.com/ErreraGraph.html (17 vertices)
I think that "Kempe's mistake" must have been that he could not prove
that his method could properly 3-color the cycle graph? I don't care
if
the cycle graph can be 3-colored or not!
regards
---Bill J.
--- Christopher Heckman |
|
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Fri Jul 14, 2006 8:04 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | Is a "coloring algorithm" really necessary in a proof of the 4CT?
No, but you usually get one as a freebie.
|
Claims, claims ... But I didn't _see_ any anywhere, except my own:
http://hdebruijn.soo.dto.tudelft.nl/fcp/index.htm
Han de Bruijn |
|
| Back to top |
|
|
icahit@gmail.com
science forum beginner
Joined: 30 Sep 2005
Posts: 24
|
| Posted: Fri Jul 14, 2006 8:42 am Post subject:
Re: Four Color Theorem
|
|
|
Is this an algorithm or a program for coloring the maps?
Cahit
Han de Bruijn wrote:
| Quote: | Proginoskes wrote:
Is a "coloring algorithm" really necessary in a proof of the 4CT?
No, but you usually get one as a freebie.
Claims, claims ... But I didn't _see_ any anywhere, except my own:
http://hdebruijn.soo.dto.tudelft.nl/fcp/index.htm
Han de Bruijn |
|
|
| Back to top |
|
|
icahit@gmail.com
science forum beginner
Joined: 30 Sep 2005
Posts: 24
|
| Posted: Fri Jul 14, 2006 9:59 am Post subject:
Re: Four Color Theorem
|
|
|
In all your examples after running greedy (algorithm) when you run
minimal coloring the outer-region of the map has received a valid
color. This at least verify my result that for any connected map the
outer-region can be taken as a part of a region of the map or more
techincally "spiral-segment" of a spiral chain of a maximal planar
graph is 3-colorable. Can you prove that this is the case in your
program for any map?
Cahit
Han de Bruijn wrote:
| Quote: | Proginoskes wrote:
Is a "coloring algorithm" really necessary in a proof of the 4CT?
No, but you usually get one as a freebie.
Claims, claims ... But I didn't _see_ any anywhere, except my own:
http://hdebruijn.soo.dto.tudelft.nl/fcp/index.htm
Han de Bruijn |
|
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Fri Jul 14, 2006 10:10 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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!.
It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.
Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.
This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.
My proof is based on the assumption that the following graph is not 4-chroma.
[The drawing below is correct in the "print" mode}
If you're going to post plain text which is supposed to line up, use a
proportional font, like Courier.
|..............| Internal chord
|--------------| External {B-C-B} Kempe chain
D <== A-----B-----C-----B------D ==> A
|--------------|--------------| External {A-C) & {C-D}
Kempe chains
The graph is planar. The {B-C-B} chain may cross the {A-C} & {C-D} chains
at common 'C' vertices.
It looks like you made Kempe's mistake again.
The graph is an attempt to find a feasible method of forcing a 4-coloring on a
chordless 5-cycle graph, without adding any chords. Without the internal chord
It is supposed to be a graph that cannot be 3-colored! With the "internal" chord,
theoretically, it cannot be properly 4-colored..
Theoretically; but (as I've told you before), if you have a planar
graph with a face of size >= 4, then there is more than one coloring.
All you have done is made one coloring fail to work; you haven't done
anything to the rest, which may still work. (In fact, in the graph G
with a pentagon, there are at least 2^(5-3) = 8 colorings. I'm not sure
whether this counts permutation of the colors or not.)
[BTW , 2^(5-3) = 4 not 8]
My point still holds.
A 3-coloring of the pentagon (P) does not work because G would be
4-colorable. A 5-coloring of P does not work because H would not be
4-colorable. If there is only one 4-coloring, all the others must be
3-colorings or 5-colorings, which inherently don't work!
Nice speech, but it also shows that you aren't on topic here. (Later
on, I do agree that in a minimal counterexample, the pentagon P will be
4-colored, and there's only one way to do that, up to isomorphism and
changing colors.)
The point is: You can't assume there is only one coloring of G-v.
|
I am not assuming a single coloring for G-v! I am only assuming a
single
coloring for P. Any coloring of G-v is acceptable as long as it
results in a
4-coloring of P. If there is a coloring of G-v that does not result in
a
4-coloring of P, then G wil be 4-colorable!
| Quote: |
You get a coloring C from the minimality of G, and show that there is a
graph H where the coloring C doesn't work. However, there _are_ other
colorings of G-v which are proper for H.
|
Are you saying that after the internal chord is added to P, that the
graph H
can arbitrarily be recolored to make P 4-colored again? In that case
you
would have to recolor one of the vertices at the end of the chord. But
which
one? Why one and not the other? If either, why not both? If both,
then
P is 3-colorable and G is 4-colorable.
| Quote: | I still say that there is only one 4-coloring of a pentagon.
That is true.
I have not made it fail. I jusr have not found the configuration that will
make it work.
Just for discussion, suppose you or I find a configuration that does work?
Then I add a couple of chords to maximize graph H. Graph H still has
fewer vertices than G. If H is not 4-colorable, then G is not an mce
because it is not minimum. One of the chords connects two vertices
with the same color. Unless one or more of the vertices of H can be
recolored, H is not properly 4-colorable. And if one or more vertices can
be recolored, then perhaps H can be properly 3-colored.
How can I make you understand what I am trying to do?
Essentially, a 4-coloring of the pentagon (P) is the only way to make graph H
4-colorable and graph G not 4-colorable! If P is 4-colorable, then two vertices
have the same color. If a chord is added between these two vertices, H will
still be smaller than G. This chord makes the colorability of H uncertain.
If P is 3-colorable, then G is 4-colorable!
If H is not 4-colorable, then G is not minimal!
If P is 4-colorable, but not 3-colorable; then and only then G is an mce!
The graph has to come before the coloring. Sure, if you have a coloring
C, you can find a graph for which C is not a proper coloring. But
that's not how the 4CT is worded.
Can you explain the above observation in the context of the mce/4CT?
Imagine you have a machine M which takes, as input, a planar graph G,
and produces a 4-coloring of G as output. (If one exists.) The 4CT
simply states that for every input, there is (at least) one output;
that is, you cannot find a planar graph G that causes M to "crash".
A minimal counterexample is a graph G which crashes M, but at the same
time, M will produce an output for any graph with fewer vertices than
G.
You are taking the output of a graph G-v and coming up with a new graph
H. The output from G-v does not work for H, but that does not imply
that the machine will crash with H as an input. So you don't have your
contradiction that proves the 4CT yet.
|
If H is not 4-colorable, won't the machine crash?
----Bill J. .
| Quote: |
--- Christopher Heckman
I expect that someone will reveal the flaw. Then I will observe that
you can't force a 4-coloring without at least 3 external chains and
that this is the only way to get three chains.
With only two chains, the colors of only three vertices may be "forced"
. [Each
vertex has only two neighbors. Therefore, there are at least two
color options
for each vertex. "Forcing" means removing all but one option!]
This leaves 2 vertices whose colors cannot be forced by chains; but by some
unknown configuration?
Before I go any further, does anyone care to comment on the 3-chain configuration?
Also, any suggestions as to how a specific vertex can be forced to be a specific
color?
Exactly what was "Kempe's mistake"?
See http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm . Two
graphs for which his proof fails are given by:
http://mathworld.wolfram.com/KittellGraph.html (23 vertices)
http://mathworld.wolfram.com/ErreraGraph.html (17 vertices)
I think that "Kempe's mistake" must have been that he could not prove
that his method could properly 3-color the cycle graph? I don't care
if
the cycle graph can be 3-colored or not!
regards
---Bill J.
--- Christopher Heckman |
|
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Fri Jul 14, 2006 11:22 am Post subject:
Re: Four Color Theorem
|
|
|
icahit@gmail.com wrote:
A FREE program. With an algorithm in it. Duhh ;-)
Han de Bruijn |
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Fri Jul 14, 2006 11:31 am Post subject:
Re: Four Color Theorem
|
|
|
icahit@gmail.com wrote:
| Quote: | In all your examples after running greedy (algorithm) when you run
minimal coloring the outer-region of the map has received a valid
color. This at least verify my result that for any connected map the
outer-region can be taken as a part of a region of the map or more
techincally "spiral-segment" of a spiral chain of a maximal planar
graph is 3-colorable. Can you prove that this is the case in your
program for any map?
|
Indeed, the outer-region is taken as a part of the map. But I don't want
to - read: I can't - prove anything. My challenge has been the colouring
of real world (black & white) bitmaps with a minimal number of colours.
That's all. No more, no less. I let theorists - not me - do the theory.
Han de Bruijn |
|
| Back to top |
|
|
icahit@gmail.com
science forum beginner
Joined: 30 Sep 2005
Posts: 24
|
| Posted: Fri Jul 14, 2006 11:58 am Post subject:
Re: Four Color Theorem
|
|
|
Thanks Han. But I know another de Bruijn from T.H.E., Eindhoven who is
very well-known by his theoritical works in math and CS.
Cahit
Han de Bruijn wrote:
| Quote: | icahit@gmail.com wrote:
In all your examples after running greedy (algorithm) when you run
minimal coloring the outer-region of the map has received a valid
color. This at least verify my result that for any connected map the
outer-region can be taken as a part of a region of the map or more
techincally "spiral-segment" of a spiral chain of a maximal planar
graph is 3-colorable. Can you prove that this is the case in your
program for any map?
Indeed, the outer-region is taken as a part of the map. But I don't want
to - read: I can't - prove anything. My challenge has been the colouring
of real world (black & white) bitmaps with a minimal number of colours.
That's all. No more, no less. I let theorists - not me - do the theory.
Han de Bruijn |
|
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sat Jul 15, 2006 3:48 am Post subject:
Re: Four Color Theorem
|
|
|
Han de Bruijn wrote:
| Quote: | Proginoskes wrote:
Is a "coloring algorithm" really necessary in a proof of the 4CT?
No, but you usually get one as a freebie.
Claims, claims ... But I didn't _see_ any anywhere, except my own:
|
"Algorithm" is different from "implementation of an algorithm".
My doctoral advisor (Robin Thomas) went even further said: "You always
get an algorithm [from a proof of a result]." This is really only a
rule of thumb, however.
| Quote: | http://hdebruijn.soo.dto.tudelft.nl/fcp/index.htm
|
(1) You need to add a link to
http://www.math.gatech.edu/~thomas/FC/fourcolor.html as well; this
provides details for the Robertson/Sanders/Seymour/Thomas proof, which
also gives a quadratic-time algorithm. (Appel & Haken only got a
quartic-time algorithm.)
(2) Anyone can code a map-coloring algorithm; brute force really works
best for small N (less than, say, 20). The trick is to get an efficient
one; for large N, the AH & RSST algorithms will beat pretty much
anything else that is known.
(3) Under "Best results so far", you should also include lower bounds.
If your lower bound equals the best result so far, you've found the
best possible value.
(a) For instance, if a graph contains an odd wheel, it needs at least 4
colors. (The state of Nevada, and its neighbors, form an odd wheel, so
there is no 3-coloring of the map of the USA.)
(b) If a graph contains an odd cycle, the graph needs at least 3
colors; otherwise, only 2 are required.
(c) The conditions under which exactly 3 colors are needed are unknown,
and referred to as "The 3-Color Problem", but there are several known
results.
For instance, if a PLANAR graph has no triangles (no 3 vertices which
are all adjacent to each other), only 3 colors are needed; this was
proven by Grotzsch in 1959, with a 3-page proof found by Thomassen in
the past decade.
(4) For a very good test of your implementation, try the map at
http://mathworld.wolfram.com/images/eps-gif/AprilFourColoring_900.gif .
--- Christopher Heckman |
|
| Back to top |
|
|
icahit@gmail.com
science forum beginner
Joined: 30 Sep 2005
Posts: 24
|
| Posted: Sat Jul 15, 2006 6:26 am Post subject:
Re: Four Color Theorem
|
|
|
Agreed all and also refer to a very detailed reference-list on graph
coloring and algorithmic issues to Chiarandini's web-site:
http://www.imada.sdu.dk/~marco/
Cahit
Proginoskes wrote:
| Quote: | Han de Bruijn wrote:
Proginoskes wrote:
Is a "coloring algorithm" really necessary in a proof of the 4CT?
No, but you usually get one as a freebie.
Claims, claims ... But I didn't _see_ any anywhere, except my own:
"Algorithm" is different from "implementation of an algorithm".
My doctoral advisor (Robin Thomas) went even further said: "You always
get an algorithm [from a proof of a result]." This is really only a
rule of thumb, however.
http://hdebruijn.soo.dto.tudelft.nl/fcp/index.htm
(1) You need to add a link to
http://www.math.gatech.edu/~thomas/FC/fourcolor.html as well; this
provides details for the Robertson/Sanders/Seymour/Thomas proof, which
also gives a quadratic-time algorithm. (Appel & Haken only got a
quartic-time algorithm.)
(2) Anyone can code a map-coloring algorithm; brute force really works
best for small N (less than, say, 20). The trick is to get an efficient
one; for large N, the AH & RSST algorithms will beat pretty much
anything else that is known.
(3) Under "Best results so far", you should also include lower bounds.
If your lower bound equals the best result so far, you've found the
best possible value.
(a) For instance, if a graph contains an odd wheel, it needs at least 4
colors. (The state of Nevada, and its neighbors, form an odd wheel, so
there is no 3-coloring of the map of the USA.)
(b) If a graph contains an odd cycle, the graph needs at least 3
colors; otherwise, only 2 are required.
(c) The conditions under which exactly 3 colors are needed are unknown,
and referred to as "The 3-Color Problem", but there are several known
results.
For instance, if a PLANAR graph has no triangles (no 3 vertices which
are all adjacent to each other), only 3 colors are needed; this was
proven by Grotzsch in 1959, with a 3-page proof found by Thomassen in
the past decade.
(4) For a very good test of your implementation, try the map at
http://mathworld.wolfram.com/images/eps-gif/AprilFourColoring_900.gif .
--- Christopher Heckman |
|
|
| Back to top |
|
|
icahit@gmail.com
science forum beginner
Joined: 30 Sep 2005
Posts: 24
|
| Posted: Sat Jul 15, 2006 2:28 pm Post subject:
Re: Four Color Theorem
|
|
|
Chris!
This is particularly to you. It may lead to a breakthrough for
Steinberg's Conjecture. I like to have your views on the following:
Claim: Let G be a planar graph without 4- and 5-cycles. Consider a
spiral chain S of G (let us assume first that V(G)=V(S)). Then if for
any consecutive two edges of S at least one belongs to a triangle
(cycle of length three) then G is 3-colorable.
Cahit
Proginoskes wrote:
| Quote: | bill wrote:
Proginoskes wrote:
icahit@gmail.com wrote:
I must be careful when I give an answer to your question. Yes my proof
has not yet published but I think it has been passed through extensive
public review in the last two years. I have given several seminars in
the mathematical departments. The bottom line is that, no one yet and
I trust, no one will be given serious comments against its correctness.
I have my doubts, especially in Cahit's paper which "settles"
Steinberg's Conjecture. In particular, I derived the conditions under
which a "triangulated ring" is 3-colorable, and they do not match
Cahit's. That, and my increased workload during the academic year, have
kept me from looking at more of the problem.
What is "Steinberg's Conjecture"? What is a "triangulated ring"?
Steinberg's conjecture states that a planar graph without any cycles of
length 4 or 5 can be 3-colored.
"Triangulated ring" is a term invented by Cahit. It refers to a cycle
of length n, surrounded by triangular faces (whose 3rd vertex points
away from the cycle), then by triangular faces which point "towards"
the cycle, and then you have a cycle on the outside.
--- Christopher Heckman
It is my opinion that the proofs should be worked out in more detail.
It is true that in the final publisheable form I will have to add a few
things and delete some unneccessary figures and explain my spiral-chain
coloring algorithm in more detail, that is three-coloring of the spiral
segments and additional stuff on three-plus-one spiral chain coloring
and also adding may be a new section for the three-edge coloring of
(bridgeless) cubic planar graphs. I will going to present my proof in
the ICM2006, Madrid in August (
http://icm2006.org/v_f/web_UC.php?CodiSeccio=14&CodiTipusEvent=4sc&Ordenacio=ae&Format=UC4sc)
and based on the feedback I receive I am going to submit to a proper
journal. The only thing that I would say about Dharwadker's "proof" of
the 4CT is that there is no description of an coloring algorithm in his
proof.
Cahit
a.khanm@gmail.com wrote:
What became of your proof of the four colour theorem? Usually people
tend to make the same old mistakes in proving the elusive theorem. Have
you found any errors yet or do you still think that your proof is
correct? Another person by the name of Ashay Dharwadker has claimed to
have proven the four colour theorem but his proof never made it to a
journal. What is the current status of your proof?
icahit@gmail.com wrote:
May be the answer to Bill's question is in my response in another group
at
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1150590683
Cahit
Proginoskes wrote:
a.khanm@gmail.com 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!.
It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.
Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.
This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.
But a variation of induction is the backbone to reduction, a technique
that both Appel and Haken, and Robertson Sanders Seymour Thomas used to
find a proof.
--- Christopher Heckman |
|
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 2:53 am | All times are GMT
|
|
Bankruptcy | Debt Consolidation | Loans | Free Advertising | MPAA
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
