On Thursday, June 27, 2013 1:34:31 AM UTC-7, quasi wrote: > 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 > > > > > > > > 1 is adjacent to 8,9,0,2,3,4 > Revise 5. to read,
1=D is forced by 3=A, 8=B & 9=C > > > > >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
I was thinking 1=D then 0=E. > > > > 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? > > > > quasi
I don't have a mathematical definition. But here's one in plain lsnguage.
Forced Five Set: A connected subset of five vertices (not isomorphicc to K5), that cannot be 4-colored. Not a stretch. I had always intended that a FFS or F4S implied a forced five set (F5S}.
In the example above, vertices 0 1 7 8 9 constitute an F5S.
As to 4-colorability, I present the following conjecture.
Conjecture: Every non 4-color planar graph contains at least one subset isomorphic to F5S.