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 ]
 quasi Posts: 12,067 Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 27, 2013 5:40 PM

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

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