bill wrote: >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 4-set, since it's >> 3-colorable. >> >> As I previously noted, if a graph with 4 vertices is not >> 3-colorable, then it must be complete (that is, it must be >> isomorphic to K4). > 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. 9=C is forced by 6=D, 7=A & 8=B
You're OK up to step 4.
> 5. 1=D is forced by 7=A, 8=B & 9=C
No, 1 is not adjacent to 7.
1 is adjacent to 8,9,0,2,3,4.
>A classic example of what I call a "forced >four subset".
Four colors are already forced at step 2. If all you want to show is that at least 4 colors are needed, you can stop right there.
However if you continue past step 4 in the following way, you'll see you need a 5th color -- 4 colors is not enough.
5. 0=D is forced by 7=A, 8=B & 9=C
6. 1=E is forced by 8=B, 9=C, 0=D & 3=A
To explain the last step, note that vertex 1 is adjacent to vertices 8,9,0, so vertex 1 can't have one of the colors B,C,D. But vertex 1 is also adjacent to vertex 3, which was forced earlier in the analysis (step 2) to have color A, hence vertex 1 can't have color A either. Thus, vertex 1 can't have any of the colors A,B,C,D.
It follows that the graph is not 4-colorable.
In any case, it's now _really_ unclear what you mean by a forced 4-set. What's needed is a rigorous mathematical definition. Are you up to the task of providing such a definition using standard graph-theoretic terminology?
Once the concept of forced 4-set is clarified to the point where at least some of us understand what you're talking about, can you then state in a clear way what you're conjecturing with regard to 4-colorability or non-4-colorability?