Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: A New Graph Coloring Conjecture.
Replies: 42   Last Post: Jul 2, 2013 4:08 AM

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 28, 2013 5:33 AM

bill wrote:
>quasi wrote:
>> bill wrote:
>>

>> >Forced Five Set: A connected subset of five vertices
>> >(not isomorphic to K5), that cannot be 4-colored.

>>
>> With the definition as you've stated it, there's no such
>> thing as a forced 5-set.
>>
>> More generally, there's no such thing as a forced n-set,
>> for any positive integer n.
>>
>> To be precise, the following is true and easily proved:
>>
>> If a graph G with n vertices is not complete, then G is
>> (n-1)-colorable.
>>
>> Thus, your stated definitions of forced 4-set (F4S) and
>> forced 5-set (F5S) are badly flawed, since, if interpreted
>> literally, there are no such sets.
>>

>> >In the example above, vertices 0 1 7 8 9 constitute an F5S.
>>
>> No, not the way you've defined it.
>>
>> The entire graph (on all 10 vertices) is not 4-colorable,
>> but the subgraph determined by vertices 7,8,9,0,1 is
>> definitely 4-colorable. In other words, the subgraph
>> determined by the vertices 7,8,9,0,1 and the edges between
>> them (inherited from the original graph) _is_ 4-colorable.
>>
>> Let H be the subgraph determined by vertices 7,8,9,0,1. The
>> other vertices (vertices 2,3,4,5,6) and their edges are not
>> part of H. H has only the 5 vertices 7,8,9,0,1 and has
>> exactly 9 edges. In fact, all pairs of distinct vertices of
>> H are adjacent except for the pair 7,1. Thus, if we only
>> want to color the subgraph H (without considering vertices
>> and edges not internal to H), it can be done with 4 colors.
>> For example, using colors A,B,C,D, color the vertices
>> 7,8,9,0,1 as A,B,C,D,A respectively.
>>

>H is ******forced***** by vertices 2 3 4 5 6. As a member of
>G, H cannot be 4-colored. If H is 4-colored, then some other
>set in G will be a F5S.

Your concept of forced 5-set is as unclear as ever.

>Am I the only person who would like to see a short
>snappy proof of the 4 CT?

Sure, that would be nice.

>I hope to create a simple proof of the Four Color Theorem. In
>this context, I don't think that I will be allowed to presume
>that forced sets do not exist.

But you _will_ be expected to give a rigorous mathematical
definition of forced sets. You previously said you couldn't
do that.

>I am fairly certain that a forced set may be cited as the
>primary reason for the more common impasses.
>
>In this context; an unresolved impasse in the attempted
>4-coloring of a planar graph might be due to the presence
>of a forced set.

If you can't define forced sets in a way that others can
understand, there's not much chance that anyone would be
able to follow a proposed proof of yours of the 4CT.

quasi

Date Subject Author
6/18/13 b92057@yahoo.com
6/18/13 Tucsondrew@me.com
6/18/13 Tucsondrew@me.com
6/18/13 quasi
6/18/13 Tucsondrew@me.com
6/18/13 quasi
6/19/13 trj
6/20/13 b92057@yahoo.com
6/20/13 quasi
6/20/13 b92057@yahoo.com
6/22/13 b92057@yahoo.com
6/23/13 quasi
6/25/13 b92057@yahoo.com
6/25/13 quasi
6/25/13 b92057@yahoo.com
6/26/13 quasi
6/26/13 Brian Q. Hutchings
6/27/13 b92057@yahoo.com
6/27/13 quasi
6/27/13 b92057@yahoo.com
6/27/13 quasi
6/27/13 quasi
6/28/13 b92057@yahoo.com
6/28/13 quasi
6/28/13 b92057@yahoo.com
6/29/13 quasi
7/1/13 b92057@yahoo.com
7/2/13 quasi
6/19/13 b92057@yahoo.com
6/19/13 quasi
6/20/13 b92057@yahoo.com
6/20/13 Tucsondrew@me.com
6/21/13 quasi
6/21/13 quasi
6/22/13 b92057@yahoo.com
6/23/13 quasi
6/19/13 b92057@yahoo.com
6/20/13 quasi
6/20/13 quasi
6/20/13 Butch Malahide
6/20/13 Butch Malahide
6/19/13 b92057@yahoo.com
6/20/13 b92057@yahoo.com