quasi
Posts:
10,903
Registered:
7/15/05


Re: A New Graph Coloring Conjecture.
Posted:
Jun 27, 2013 4:38 AM


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
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 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

