quasi
Posts:
10,968
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 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

