Four Color Theorem

FAQ

Memberlist

Usergroups

Profile

Preferences

Forum index » Science and Technology » Math

Four Color Theorem

Page 3 of 6 [79 Posts]

View previous topic :: View next topic
Goto page: Previous 1, 2, 3, 4, 5, 6 Next

Author

Message

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Sun Jul 09, 2006 11:56 pm Post subject: Note

Re: Four Color Theorem

bill wrote:

Quote:

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.

Quote:

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.

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

bill
science forum Guru

Joined: 07 Sep 2005
Posts: 311

Posted: Mon Jul 10, 2006 3:29 am Post subject: Note

Re: Four Color Theorem

icahit@gmail.com wrote:

Quote:

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

The Hatcher, Green, Kimber proof discussed in the wu::forum seems to
me
to be a rehashing of Kempe's proof without addressing Heawood's
counter-example?

Consider Figure 2b in the "H/G/K proof. The proof concludes that the
two yellow
regions may be recolored to give a 3-colorable map. Actually, this
does not prove
that the two yellow regions may be recolored.

My approach is to expand the yellow regions so that they have a common
border;
creating map M*-v. If M is a counterexample, then M-v and M*-v cannot
be
3-colorable or 5-chroma. If M*-v is 3-coloable, then M is 4-colorable.
If
M*-v is 5-chroma, then M is not minmal

---Bill J

Quote:

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

icahit@gmail.com
science forum beginner

Joined: 30 Sep 2005
Posts: 24

Posted: Mon Jul 10, 2006 6:39 am Post subject: Note

Re: Four Color Theorem

I am not close Steinberg's Conjecture file yet. I hope we will again
working on it again. I hope our lemma (corrected by yourself) on the
triangulated ring would some way be used together with the spiral-chain
coloring in settleing that conjecture as well. By the way have you
heard anything new on Steinberg's conjecture newly?

Cahit

Proginoskes wrote:

Quote:

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.

It is my opinion that the proofs should be worked out in more detail.

--- Christopher Heckman

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

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Mon Jul 10, 2006 10:40 pm Post subject: Note

Re: Four Color Theorem

icahit@gmail.com wrote:

Quote:

I've been collecting information about Steinberg's Conjecture, along
with properties of such graphs. (Some day I might turn it into a
webpage.) The latest result that I know of is:

O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour,
"Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable",
J. of Combinatorial Theory (Series B), 93:303-311, 2005.

Link: http://www.cs.ualberta.ca/~mreza/research/stein3.ps

I've been wondering about a question that Craig Tovey asked me during
my doctoral defense: If you have a planar graph G without 4- and
5-cycles, can you use the "difficult graphs" technique to find out how
big of an independent set can you find? If the answer is at least n/3,
then you have a weaker version of Steinberg's Conjecture. OTOH, if the
answer is less than n/3, you've disproven Steinberg's Conjecture.

--- Christopher Heckman

Quote:

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.

It is my opinion that the proofs should be worked out in more detail.

--- Christopher Heckman

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

icahit@gmail.com
science forum beginner

Joined: 30 Sep 2005
Posts: 24

Posted: Tue Jul 11, 2006 9:51 am Post subject: Note

Re: Four Color Theorem

Quote:

icahit@gmail.com wrote:
I am not close Steinberg's Conjecture file yet. I hope we will again
working on it again. I hope our lemma (corrected by yourself) on the
triangulated ring would some way be used together with the spiral-chain
coloring in settleing that conjecture as well. By the way have you
heard anything new on Steinberg's conjecture newly?

I've been collecting information about Steinberg's Conjecture, along
with properties of such graphs. (Some day I might turn it into a
webpage.) The latest result that I know of is:

O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour,
"Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable",
J. of Combinatorial Theory (Series B), 93:303-311, 2005.

Link: http://www.cs.ualberta.ca/~mreza/research/stein3.ps

I've been wondering about a question that Craig Tovey asked me during
my doctoral defense: If you have a planar graph G without 4- and
5-cycles, can you use the "difficult graphs" technique to find out how
big of an independent set can you find? If the answer is at least n/3,
then you have a weaker version of Steinberg's Conjecture. OTOH, if the
answer is less than n/3, you've disproven Steinberg's Conjecture.

--- Christopher Heckman

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.

It is my opinion that the proofs should be worked out in more detail.

--- Christopher Heckman

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

icahit@gmail.com
science forum beginner

Joined: 30 Sep 2005
Posts: 24

Posted: Tue Jul 11, 2006 9:55 am Post subject: Note

Re: Four Color Theorem

Correction!

ica...@gmail.com wrote:

Quote:

I know that paper which is again based on dischraging methods. I am
going to think of your question. Meanwhile I am trying to give answers
to these: 1) For any given triangulated planar graph in what way we can
delete minimum number of edges so that the resulting planar G' graph is
3-colorable, 2) Can we use spiral-chains in finding or chracterizing
the planar graph G' and 3) Is the class of 3-colorable planar graphs
{G'} cover all planar graphs without 4- and 5-cycles?

Cahit

Proginoskes wrote:
icahit@gmail.com wrote:
I am not close Steinberg's Conjecture file yet. I hope we will again
working on it again. I hope our lemma (corrected by yourself) on the
triangulated ring would some way be used together with the spiral-chain
coloring in settleing that conjecture as well. By the way have you
heard anything new on Steinberg's conjecture newly?

I've been collecting information about Steinberg's Conjecture, along
with properties of such graphs. (Some day I might turn it into a
webpage.) The latest result that I know of is:

O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour,
"Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable",
J. of Combinatorial Theory (Series B), 93:303-311, 2005.

Link: http://www.cs.ualberta.ca/~mreza/research/stein3.ps

I've been wondering about a question that Craig Tovey asked me during
my doctoral defense: If you have a planar graph G without 4- and
5-cycles, can you use the "difficult graphs" technique to find out how
big of an independent set can you find? If the answer is at least n/3,
then you have a weaker version of Steinberg's Conjecture. OTOH, if the
answer is less than n/3, you've disproven Steinberg's Conjecture.

--- Christopher Heckman

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.

It is my opinion that the proofs should be worked out in more detail.

--- Christopher Heckman

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

bill
science forum Guru

Joined: 07 Sep 2005
Posts: 311

Posted: Wed Jul 12, 2006 9:08 pm Post subject: Note

Re: Four Color Theorem

Proginoskes wrote:

Quote:

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..

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?

Quote:

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

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Thu Jul 13, 2006 5:32 am Post subject: Note

Re: Four Color Theorem

icahit@gmail.com wrote:

Quote:

It depends. Any "even triangulation" (a triangulation where every
vertex has even degree) is 3-colorable. In fact, there is an old
characterization of when a planar graph G is 3-colorable: iff there is
an even triangulation T which contains G.

Quote:

2) Can we use spiral-chains in finding or chracterizing
the planar graph G' and 3) Is the class of 3-colorable planar graphs
{G'} cover all planar graphs without 3- and 4-cycles?

I think you mean 4- and 5-cycles here; any triangle-free planar graph
is 3-colorable (Grotzsche's Theorem, 1959; Carsten Thomassen has given
a 3-page proof of this fact).

--- Christopher Heckman

Quote:

Proginoskes wrote:
icahit@gmail.com wrote:
I am not close Steinberg's Conjecture file yet. I hope we will again
working on it again. I hope our lemma (corrected by yourself) on the
triangulated ring would some way be used together with the spiral-chain
coloring in settleing that conjecture as well. By the way have you
heard anything new on Steinberg's conjecture newly?

I've been collecting information about Steinberg's Conjecture, along
with properties of such graphs. (Some day I might turn it into a
webpage.) The latest result that I know of is:

O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour,
"Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable",
J. of Combinatorial Theory (Series B), 93:303-311, 2005.

Link: http://www.cs.ualberta.ca/~mreza/research/stein3.ps

I've been wondering about a question that Craig Tovey asked me during
my doctoral defense: If you have a planar graph G without 4- and
5-cycles, can you use the "difficult graphs" technique to find out how
big of an independent set can you find? If the answer is at least n/3,
then you have a weaker version of Steinberg's Conjecture. OTOH, if the
answer is less than n/3, you've disproven Steinberg's Conjecture.

--- Christopher Heckman

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.

It is my opinion that the proofs should be worked out in more detail.

--- Christopher Heckman

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

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Thu Jul 13, 2006 5:36 am Post subject: Note

Re: Four Color Theorem

bill wrote:

Quote:

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.)

--- 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

icahit@gmail.com
science forum beginner

Joined: 30 Sep 2005
Posts: 24

Posted: Thu Jul 13, 2006 12:19 pm Post subject: Note

Re: Four Color Theorem

I am aware of these results, i.e., even triangulations and
triangle-free planar graphs are 3-colorable. But there are some other
planar graphs which are not even triangulation or triangle-free but
still 3-colorable. Take for example a chromatic critical (planar) graph
G (here critical means by deletion of any vertex result a decrease in
chromatic index of the original graph G). Now consider spiral-chain
coloring of G which is 4 colorable. I suspect that except the last
vertex in the spiral-chain all other vertices of G are 3-colorable or
perhaps I will need an counterexample that chromatic critical planar
graphs with more than one four colored vertices. Then we may develop a
method to show that all planar graphs without 4 and 5-cycles are
3-colorable. I put a figure in my "map coloring site" about this idea
in the photo gallery at http://www.flickr.com/photos/49058045@N00/
under the title Steinberg.

Proginoskes wrote:

Quote:

icahit@gmail.com wrote:
I know that paper which is again based on dischraging methods. I am
going to think of your question. Meanwhile I am trying to give answers
to these: 1) For any given triangulated planar graph in what way we can
delete minimum number of edges so that the resulting planar G' graph is
3-colorable,

It depends. Any "even triangulation" (a triangulation where every
vertex has even degree) is 3-colorable. In fact, there is an old
characterization of when a planar graph G is 3-colorable: iff there is
an even triangulation T which contains G.

2) Can we use spiral-chains in finding or chracterizing
the planar graph G' and 3) Is the class of 3-colorable planar graphs
{G'} cover all planar graphs without 3- and 4-cycles?

I think you mean 4- and 5-cycles here; any triangle-free planar graph
is 3-colorable (Grotzsche's Theorem, 1959; Carsten Thomassen has given
a 3-page proof of this fact).

--- Christopher Heckman

Proginoskes wrote:
icahit@gmail.com wrote:
I am not close Steinberg's Conjecture file yet. I hope we will again
working on it again. I hope our lemma (corrected by yourself) on the
triangulated ring would some way be used together with the spiral-chain
coloring in settleing that conjecture as well. By the way have you
heard anything new on Steinberg's conjecture newly?

I've been collecting information about Steinberg's Conjecture, along
with properties of such graphs. (Some day I might turn it into a
webpage.) The latest result that I know of is:

O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour,
"Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable",
J. of Combinatorial Theory (Series B), 93:303-311, 2005.

Link: http://www.cs.ualberta.ca/~mreza/research/stein3.ps

I've been wondering about a question that Craig Tovey asked me during
my doctoral defense: If you have a planar graph G without 4- and
5-cycles, can you use the "difficult graphs" technique to find out how
big of an independent set can you find? If the answer is at least n/3,
then you have a weaker version of Steinberg's Conjecture. OTOH, if the
answer is less than n/3, you've disproven Steinberg's Conjecture.

--- Christopher Heckman

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.

It is my opinion that the proofs should be worked out in more detail.

--- Christopher Heckman

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

bill
science forum Guru

Joined: 07 Sep 2005
Posts: 311

Posted: Thu Jul 13, 2006 9:17 pm Post subject: Note

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.

|..............| 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]

I still say that there is only one 4-coloriing of a pentagon.

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!

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

bill
science forum Guru

Joined: 07 Sep 2005
Posts: 311

Posted: Thu Jul 13, 2006 10:58 pm Post subject: Note

Re: Four Color Theorem

Proginoskes wrote:

Quote:

What is "Steinberg's Conjecture"? What is a "triangulated ring"?

regards

---Bill J

Quote:

It is my opinion that the proofs should be worked out in more detail.

--- Christopher Heckman

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

bill
science forum Guru

Joined: 07 Sep 2005
Posts: 311

Posted: Thu Jul 13, 2006 11:03 pm Post subject: Note

Re: Four Color Theorem

icahit@gmail.com wrote:

Quote:

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.
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.

Is a "coloring algorithm" really necessary in a proof of the 4CT?

regards

---Bill J

Quote:

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

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Thu Jul 13, 2006 11:54 pm Post subject: Note

Re: Four Color Theorem

bill wrote:

Quote:

No, but you usually get one as a freebie.

--- Christopher Heckman

Quote:

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Thu Jul 13, 2006 11:57 pm Post subject: Note

Re: Four Color Theorem

bill wrote:

Quote:

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

Quote:

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

Google

Display posts from previous:

Page 3 of 6 [79 Posts]

Goto page: Previous 1, 2, 3, 4, 5, 6 Next
View previous topic :: View next topic

The time now is Sat Jan 10, 2009 2:18 am | All times are GMT

Forum index » Science and Technology » Math