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 ]
 b92057@yahoo.com Posts: 1,187 Registered: 4/18/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 28, 2013 3:48 AM

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