quasi
Posts:
12,052
Registered:
7/15/05


Re: A New Graph Coloring Conjecture.
Posted:
Jun 18, 2013 11:36 PM


Zeit Geist wrote: >quasi wrote: >> bill wrote: >> > >> >Conjecture: A graph is fourcolorable, 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 4colorable.
I'll ask the question this way:
Does there exist a finite set of non4colorable graphs such that, if a given graph G has no subgraphs isomorphic to one of those graphs, then G is 4colorable?
Another way to ask the question is this:
Consider the set of non4colorable graphs such that every proper subgraph is 4colorable. 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

