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 18, 2013 11:36 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Zeit Geist wrote:
>quasi wrote:
>> bill wrote:
>> >
>> >Conjecture: A graph is four-colorable, if it does not contain
>> >a complete K5 sub graph.

>>
>> I think the following works as a counterexample ...
>>
>> Let G = (V,E) where
>>
>> ...
>>
>> Therefore, if I haven't made an error, G serves as a
>> counterexample to the stated claim.

>
>You are correct.
>
>So, I am wondering,
>
>What it is that the OP, bill, is investigating?


I guess he's trying to find a simple test to determine whether
or not a given graph G is 4-colorable.

I'll ask the question this way:

Does there exist a finite set of non-4-colorable graphs such
that, if a given graph G has no subgraphs isomorphic to one of
those graphs, then G is 4-colorable?

Another way to ask the question is this:

Consider the set of non-4-colorable graphs such that every
proper subgraph is 4-colorable. Are there only finitely many
such graphs, up to isomorphism?

I think it's clear that the two questions above are equivalent,
and I'm fairly sure that the answer to those question is no.

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.