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

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 ]
b92057@yahoo.com

Posts: 1,187
Registered: 4/18/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 25, 2013 4:46 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Sunday, June 23, 2013 2:54:53 AM UTC-7, quasi wrote:
> 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


I can show a forced 4 set in your graph if you are interested. Otherwise, I
have no objection to ending this diatribe.

bill.
bill


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.