Date: Jun 18, 2013 11:36 PM
Subject: Re: A New Graph Coloring Conjecture.
Zeit Geist 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.