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 ]
b92057@yahoo.com

Posts: 1,187
Registered: 4/18/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 28, 2013 3:48 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Thursday, June 27, 2013 2:38:03 PM UTC-7, quasi wrote:
> bill wrote:
>
>
>

> >Forced Five Set: A connected subset of five vertices
>
> >(not isomorphicc 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.
>
>
>
> quasi


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.

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



On Thursday, June 27, 2013 2:38:03 PM UTC-7, quasi wrote:
> bill wrote:
>
>
>

> >Forced Five Set: A connected subset of five vertices
>
> >(not isomorphicc 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.
>
>
>
> quasi


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

bill




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.