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,232
Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 25, 2013 6:08 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

bill wrote:
>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.

>
>I can show a forced 4 set in your graph if you are interested.


By a forced 4-set, it seems you mean a subgraph isomorphic
to K4. If so, there's no need to show me that my examples
contain such subgraphs since I already said that my examples
had subgraphs isomorphic to K4.

But I also noted (do you actually _read_ replies?) that your
two conjectures did not explicitly prohibit subgraphs isomorphic
to K4. Rather they prohibited subgraphs isomorphic to K5. So my
examples met your stated restrictions.

If you now want to change your restrictions to prohibit
subgraphs isomorphic to K4, fine, but then Butch Malahide's
examples disprove your conjecture, consistent with this new
restriction.

In any case, I challenged you to give a complete, rigorous
mathematical statement of what you are currently claiming,
but so far, no response from you.

>Otherwise, I have no objection to ending this diatribe.

Probably a good idea.

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.