Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: A New Graph Coloring Conjecture.
Replies: 42   Last Post: Jul 2, 2013 4:08 AM

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 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 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.

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

quasi

Date Subject Author
6/18/13 b92057@yahoo.com
6/18/13 Tucsondrew@me.com
6/18/13 Tucsondrew@me.com
6/18/13 quasi
6/18/13 Tucsondrew@me.com
6/18/13 quasi
6/19/13 trj
6/20/13 b92057@yahoo.com
6/20/13 quasi
6/20/13 b92057@yahoo.com
6/22/13 b92057@yahoo.com
6/23/13 quasi
6/25/13 b92057@yahoo.com
6/25/13 quasi
6/25/13 b92057@yahoo.com
6/26/13 quasi
6/26/13 Brian Q. Hutchings
6/27/13 b92057@yahoo.com
6/27/13 quasi
6/27/13 b92057@yahoo.com
6/27/13 quasi
6/27/13 quasi
6/28/13 b92057@yahoo.com
6/28/13 quasi
6/28/13 b92057@yahoo.com
6/29/13 quasi
7/1/13 b92057@yahoo.com
7/2/13 quasi
6/19/13 b92057@yahoo.com
6/19/13 quasi
6/20/13 b92057@yahoo.com
6/20/13 Tucsondrew@me.com
6/21/13 quasi
6/21/13 quasi
6/22/13 b92057@yahoo.com
6/23/13 quasi
6/19/13 b92057@yahoo.com
6/20/13 quasi
6/20/13 quasi
6/20/13 Butch Malahide
6/20/13 Butch Malahide
6/19/13 b92057@yahoo.com
6/20/13 b92057@yahoo.com