Re: Doubt - Proof of Four Color Theorem


Proginoskes wrote:

> (1) It doesn't check for loops. Like I said, if you have a graph with
> loops, it cannot be colored at all.

What exactly do you mean by loops, if you mean self loops then there is
no need to verify it.Look at my algorithm and then decide whether it
can color loops or not,

Fisrt I start from some vertex and traverse the whole graph , and
at each vertex see the colors of the adjacent vertices and then color
the given vertex with "least" Color code. Since I am coloring the graph
using least color code when you consider a path color of the vertices
will either lie in 1 and 2 or sometimes at 3.if you find a wheel then
it will use the 4th color code to color the center of the wheel.

> (2) Your algorithm only colors graphs with <= 50 vertices. It has been
> proven (sorry, I forgot by whom) that every loopless planar graph
> with <= 50 vertices is 4-colorable, independent of the Appel-Haken
> and Robertson-Sanders-Seymour-Thomas. Thus your program proves
> nothing if it works, and if it doesn't work, it proves even less.

This may be stupid , but please can you tell me how can you say that my
program can color only graphs with <=50 vertices.


> (3) The user verifies the answer. It takes almost no effort to let the
> machine verify the coloring is proper. This would at least save you
> the embarassment of saying that a certain coloring works when it
> actually doesn't.
> If your algorithm really 4-colors all planar graphs, the user doesn't
> have
> to do all of this.

Actually I wasn't much clear when i stated my problem before, user just
has to verify whether the graph is planar or not and not whether the
graph is four colorable or not.


> If you can prove it always works; i.e., you prove the algorithm is
> correct.
>
> A few years ago, Mark Provo came up with an algorithm for Goldbach's
> Conjecture:
>
> Input: an even number N >= 4.
> Output: a correct statement that said whether there are two prime
> numbers
> p and q such that p + q = N.
>
> Algorithm (pseudocode):
>
> If N <= 10, return TRUE
> For p = 5 to N - 3 step 2
> If (p is prime) and (N - p is prime)
> return TRUE
> Return FALSE
>
>
> (It also checked congruence mod 6 before checking primality; I've
> included that in the primality test here.)
>
> He claimed he had thus solved the Goldbach Conjecture, based on this
> algorithm.
>
> What he failed to do was to prove that the output is always TRUE; this
> is why he didn't have a proof, and neither do you.

I have stated my algorithm above , do you think that this algorithm
1) will not work on all the planar graphs
2) isn't enough proof.

regards,
anand b

.

Relevant Pages
Quantcast