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 8:23 PM

On Friday, June 28, 2013 2:20:24 AM UTC-7, quasi wrote:
> 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.
>

Give me the mathematical definition of an impasse and
I will try to adopt it to include forced sets.
>
>

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

Can you accept this definition?

No?

Consider;

Impasse. A difficulty encountered in the attempted
four coloring of a graph.

Type I " An impasse that is created by the presence of a vertex adjacent to four other vertices, each of which has an assigned color that is different from the assigned color any of the three other vertices".

Type II "All other impasses."

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