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 ]
 b92057@yahoo.com Posts: 1,187 Registered: 4/18/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 22, 2013 10:36 PM

On Wednesday, June 19, 2013 9:25:28 PM UTC-7, quasi wrote:
> bill wrote:
>

> >
>
> >Okay.
>
> >
>
> >Finite planar graphs are 4-C because they cannot
>
> >contain subgraphs isomorphic to K5!
>
> >
>
> >My thinking is thus. In any K4 subgraph one vertex is
>
> >unavailable. Therefore, there is no way to force any set of
>
> >4 vertices to have four different colors. Tangled chains are
>
> >not due to the congiguration of the graph but result from a
>
> >fortuitous coloring. Plus, if two chains are tangled; there
>
> >will be two that are not tangled.
>
> >
>
> >If there are no forceable sets of four vertices, the graph
>
> >must be 4 colorable.
>
>
>
> Except that I've already shown you a counterexample.
>
>
>
> quasi

If I understand correctly, your counterexample
proves the 4CT to be false. Evidently your
are also considering non-planar graphs.

Is your counterexample a non 4-colorable, non-planar graph without no forceable four
vertex sets?

But that doesn't make any sense.

Perhaps I have not explained "forceable" sets
sufficiently. A forceable 4-set is set of four vertices that cannot be 3-colored. The complete graph on four vertices is such a set.

Also, all four vertices must be connected to the same external vertex.

bill
>
>

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