
Re: A New Graph Coloring Conjecture.
Posted:
Jun 28, 2013 3:48 AM


On Thursday, June 27, 2013 2:38:03 PM UTC7, quasi wrote: > bill wrote: > > > > >Forced Five Set: A connected subset of five vertices > > >(not isomorphicc to K5), that cannot be 4colored. > > > > With the definition as you've stated it, there's no such > > thing as a forced 5set. > > > > More generally, there's no such thing as a forced nset, > > 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 > > (n1)colorable. > > > > Thus, your stated definitions of forced 4set (F4S) and > > forced 5set (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 4colorable, but > > the subgraph determined by vertices 7,8,9,0,1 is definitely > > 4colorable. 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_ 4colorable. > > > > 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 4colored.
If H is 4colored, 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 UTC7, quasi wrote: > bill wrote: > > > > >Forced Five Set: A connected subset of five vertices > > >(not isomorphicc to K5), that cannot be 4colored. > > > > With the definition as you've stated it, there's no such > > thing as a forced 5set. > > > > More generally, there's no such thing as a forced nset, > > 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 > > (n1)colorable. > > > > Thus, your stated definitions of forced 4set (F4S) and > > forced 5set (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 4colorable, but > > the subgraph determined by vertices 7,8,9,0,1 is definitely > > 4colorable. 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_ 4colorable. > > > > 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 4coloring of a planar graph might be due to the presence of a forced set.
bill

