
Re: A New Graph Coloring Conjecture.
Posted:
Jun 20, 2013 12:10 AM


On Tuesday, June 18, 2013 8:21:53 PM UTC7, quasi wrote: > 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. > javascript:; > > > quasi
Okay.
Finite planar graphs are 4C because they cannot contain subgraphs isomorphic to K5!
My thinking is thus. In any K4 subgraph one vertex is unavailable. Therefore, there is no way to force any set of 4 vertices to have four different colors. Tangled chains are not due to the congiguration of the graph but result from a fortuitous coloring. Plus, if two chains are tangled; there will be two that are not tangled.
If there are no forceable sets of four vertices, the graph must be 4 colorable.
bill,

