Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
quasi

Posts: 9,888
Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 28, 2013 5:33 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
Read A New Graph Coloring Conjecture.
b92057@yahoo.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
trj
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/25/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/26/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/26/13
Read Re: A New Graph Coloring Conjecture.
Brian Q. Hutchings
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/28/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/29/13
Read Re: A New Graph Coloring Conjecture.
quasi
7/1/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
7/2/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/19/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.