Re: Doubt - Proof of Four Color Theorem



> Then the program you wrote isn't for general planar graphs, is it? A
> program to 4-color an arbitrary planar graph takes the graph G and
> proves a coloring of G.

My program can properly color the vertices ( not regions ) of any
planar graph using 4 or less colors.The program works fine with planar
graph of maximum degree 6.


> Your program appears to input a graph with maximum degree <= 3 and
> 4-colors it. Thus, at the very most, the only thing that your program
> can "prove" is:
>
> THEOREM. Let G be a graph with maximum degree <= 3. Then G can be
> 4-colored.
>
> This is NOT the Four Color Theorem.
>
> * BTW, the error in your paper is the statement that d_MAX of H is also
> 3. In fact, there's a counterexample in your own paper. In fig (b), you
> will have a vertex in H corresponding to the 8-cycle (octagon) in the
> middle of the picture, so H will have a vertex of degree 8. 8 is not <=
> 3.
>
> --- Christopher Heckman

I agree Imade a mistake in my paper.But my approach to the same problem
is new.There is some prerequistes to be done to obtain the 4 coloration
of the planar graph using my program, they are,

1) Call the planar graph to be 4 colored as G.
2) Obtain the dual of graph G and call it H.Since graph G is planar
graph H is also planar.
3) ( Correction in my paper ) The maximum degree of H is not <=3.
4) Remove self loops and parallel edges in graph H.
5) By executing the previous step the connectivity of the graph H will
not be altered.
6) Input the modified graph H to my program.
7) obtain the color sequence for the proper coloring of the vertices of
graph H.
8) Comparing the graphs G and H , we can conclude that the act of
properly coloring the vertices of graph H using 4 or less colors is
same as properly coloring the regions of graph G using 4 or less
colors.

Thus in the end you will have proper coloring sequence for the graph G.

.

Relevant Pages