
Re: A New Graph Coloring Conjecture.
Posted:
Jun 27, 2013 12:10 AM


On Wednesday, June 26, 2013 12:49:42 AM UTC7, quasi wrote: > Bill wrote: > > > > >I took a second look at your graph information. When I say > > >those virtually invisible dots, I had enough to analyze the > > >graoh for FFS. I found one. It is vetices 1 7 8 9. Not a K4. > > > > Right, the subgraph determined by vertices 1,7,8,9 is not a > > K4, but it's not what you call a forced 4set, since it's > > 3colorable. > > > > As I previously noted, if a graph with 4 vertices is not > > 3colorable, then it must be complete (that is, it must be > > isomorphic to K4). > > > > quasi 1 4 4 7 7 . 2 4 5 7 \ . 2 5 6 7 = 3 .  \ 8 3 4 8 5  .  \ ./ 3 5 8 6  0 . \/  3 6 9 4  .  . \  4 5  .  /.\ 4 6 2/9 5 6 .  / . . / . 1 ANALYSIS; 1. Arbitrarily assign colors initial colors; 4=B 5=C 6=D
2. This forces 3=A & 7=A.
3. 8=B is forced by 7=A 5=C & 6=D
4. 9C is forced by 6=D, 7=A & 8=B
5. 1=D is forced by 7=A, 8=B & 9=C
A classic example of what I call a "forced four subset".
bill

