Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 quasi Posts: 12,018 Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 23, 2013 5:57 AM

bill wrote:

>If I understand correctly, your counterexample proves the 4CT
>to be false.

No, you don't understand correctly.

My examples don't disprove the 4-Color Conjecture.

They disprove _your_ conjectures.

If a graph contains no subgraph isomorphic to K5, then
it's 4-colorable,

In reply, I defined a graph G such that:

(1) G contains no subgraph isomorphic to K5.

(2) G is not 4-colorable.

The graph G thus disproves your conjecture.

Of course G is non-planar.

Any counterexample to your conjecture must be non-planar.

If a graph has no vertex with degree less than 5 and no
subgraph isomorphic to K5, then it's 4-colorable.

In reply, I defined a graph G such that:

(1) G has no vertex with degree less than 5.

(2) G contains no subgraph isomorphic to K5.

(3) G is not 4-colorable.

The graph G thus disproves your revised conjecture.

And once again, G is non-planar.

It appears that you did not understand either of the
counterexamples I posted.

You repeatedly asked if my examples are non-planar. Of course,
they are. I said as much several times. Moreover, they _had_
to be. Any counterexample to either of your conjectures must
be non-planar.

>Evidently your are also considering non-planar graphs.

Yes, of course.

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

No.

My examples were non 4-colorable and of course non-planar,
but both of my examples had subgraphs isomorphic to K4.

However, your conjectures never specified no K4s.

You only specified no K5s.

Both of my examples had no K5s.

Thus, I disproved your first two conjectures, as they were
originally stated.

Now it appears that you want to revise the conjecture still
further.

Your current conjecture seems to be:

If a graph has no vertex with degree less than 5 and no
subgraph isomorphic to K4, then it's 4-colorable.

But that conjecture is also false.

the existence of a graph G such that

(1) G has no vertex with degree less than 5.

(2) G does not contain any triangles (G has no K3s).

(3) G is not 4-colorable.

It appears you didn't understand his example either.

>But that doesn't make any sense.

Try to understand Butch Malahide's examples.

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

That's the _only_ such set, up to isomorphism.

More precisely:

If a graph G has a 4-point subgraph H such that H is not
3-colorable, then H is isomorphic to K4.

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

If you do that, then you get a K5.

I thought your conjectures specified no K5s.

I think there's a communication gap here.

In any case, so far, all your conjectures in this thread have
been disproved. All of them.

If you have a new conjecture with revised conditions, you need
to state it carefully and completely, otherwise further
discussion is pointless.

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