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