
Re: A New Graph Coloring Conjecture.
Posted:
Jun 27, 2013 4:45 PM


On Thursday, June 27, 2013 1:34:31 AM UTC7, 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 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). > > > 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 4colorable. > > > > In any case, it's now _really_ unclear what you mean by a forced > > 4set. What's needed is a rigorous mathematical definition. Are > > you up to the task of providing such a definition using standard > > graphtheoretic terminology? > Once the concept of forced 4set 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 4colorability or non4colorability? > > > > 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 4colored. 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 4colorability, I present the following conjecture. Conjecture: Every non 4color planar graph contains at least one subset isomorphic to F5S.
bill

