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


On Jun 20, 3:17 pm, Butch Malahide <fred.gal...@gmail.com> wrote: > 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.
Duh. You don't need Ramsey's theorem for that construction, and it suffices to take N = 2^n instead of N = floor(n!e). Given a coloring f:V > [n], define C(z) = {f(x,z): x < z} subseteq [n]. By the pigeonhole principle there exist y & z, 0 <= y < z, with C(y) = C(z). Let c = f(y,z) in C(z); then c in C(y), and so there exists x < y with f(x,y) = c = f(y,z), i.e., the coloring is improper.

