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,012 Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 25, 2013 6:08 PM

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

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

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

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