Re: Doubt - Proof of Four Color Theorem


anand_bheemaraju@xxxxxxxxx wrote:
> 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,

I mean an edge, both of whose ends are the same vertex. You have on in
the upper-left hand corner of the figure in your .pdf file.

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

Ah, yes, the greedy algorithm. It's been proven it doesn't always give
you a k-coloring when k is the chromatic number of G.

(I'm looking at another alleged proof of the 4CT, which uses "spiral
chains". I've talked with the author, and he claims that spiral chains,
which is a way to traverse the graph and choose an ordering of the
vertices. I haven't decided whether it works or not, but I've found
errors in his papers. Big ones. Especially in the one about Steinberg's
Conjecture, which says that every planar graph without 4- or 5-cycles
is 3-colorable.)

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

Mea culpa. I saw the
int listColor[50];
declaration and thought that was the array you're using for the
coloring.

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

Looking at the code, the for(...) loop around the statement
node->setColor(i);
I noticed that if you can't 4-color a vertex (which is the only place
where a vertex is colored), then the algorithm doesn't say anything,
and what it gives is worthless, while saying that the output is really
a 4-coloring.

In short, the algorithm operates as if the ordering of the vertices
will actually give a 4-coloring: The algorithm (in particular, the
for(...) loop I mentioned) assumes its output is correct while it's
running.

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

It'll work on some of them. For instance, if the graph has at most 4
vertices, it will work.

> 2) isn't enough proof.

It isn't proof. It lies, in that it claims there is a 4-coloring but
maybe it can't produce it. You need to actually show that it gives the
right answer 100% of the time; 99% doesn't count.

--- Christopher Heckman

.

Relevant Pages

  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)
  • Re: Vertex Cover implementation
    ... i code this simple greedy algorithm for the vertex cover: ... As you are constructing your graph you can update the vertex ... each edge appears on two adjacency lists. ... reason to use a priority queue for your algorithm. ...
    (comp.theory)
  • Re: Doubt - Proof of Four Color Theorem
    ... > loops, it cannot be colored at all. ... Fisrt I start from some vertex and traverse the whole graph, ... > If your algorithm really 4-colors all planar graphs, ...
    (sci.math)
  • Re: combinatorial optimization problem (six-pick wager grouping)
    ... versed in graph theoretic approaches could comment on my ideas below - ... I'n not a graph theorist, nor a graph algorithm buff, so I can't really ... attempt to merge it with each bet already in the pool. ... million edges when I ignored wager size. ...
    (comp.programming)
Loading