Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
quasi

Posts: 10,226
Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 23, 2013 5:57 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.

Your initial conjecture:

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.

Your revised conjecture:

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.

Butch Malahide has already shown (earlier in this thread)
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
Read A New Graph Coloring Conjecture.
b92057@yahoo.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
trj
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/25/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/26/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/26/13
Read Re: A New Graph Coloring Conjecture.
Brian Q. Hutchings
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/28/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/29/13
Read Re: A New Graph Coloring Conjecture.
quasi
7/1/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
7/2/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/19/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.