
Re: A New Graph Coloring Conjecture.
Posted:
Jun 20, 2013 4:17 PM


On Jun 20, 3:27 am, quasi <qu...@null.set> wrote: > bill wrote: > >bill wrote: > > >> Conjecture: A graph is fourcolorable, if it does not contain > >> a complete K5 sub graph. > > >Suppose I caveat no vertices with degree < 5? > > Stated in full, your question is this: > > If a graph has no vertex with degree less than 5 and no > subgraph isomorphic to K5, must it be 4colorable? > > The answer is no. > > Define a graph G = (V,E) as follows [...]
It is well known that there are graphs of arbitrarily high chromatic number with no subgraph isomorphic to K_3. There are many ways of constructing such graphs; here's a pretty one using Ramsey's theorem. Consider a fixed natural number n (this works for infinite cardinals too but never mind); we want a trianglefree graph G = (V,E) which is not ncolorable. Choose N large enough so that any coloring of the edges of K_{N+1} with n colors contains a monochromatic triangle; e.g., N = floor(n!e) will do the trick. Let V = {(x,y) in omega times omega: 0 <= x < y <= N}, E = {{(x,y),(y,z)}: x < y < z}.
If for some reason you want the minimum degree to be at least 5, a slight modification takes care of that: V = {(x,y) in omega times omega: 0 <= x < y <= N+5 and y  x <= N}.
Actually, if you have a graph of chromatic number n > 5, deleting vertices of degree < 5 is not going to change the chromatic number.

