Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: A New Graph Coloring Conjecture.
Replies: 42   Last Post: Jul 2, 2013 4:08 AM

 Messages: [ Previous | Next ]
 Butch Malahide Posts: 894 Registered: 6/29/05
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 four-colorable, 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 4-colorable?

>
> > 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 triangle-free graph G = (V,E) which is
> not n-colorable. 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.

Date Subject Author
6/18/13 b92057@yahoo.com
6/18/13 Tucsondrew@me.com
6/18/13 Tucsondrew@me.com
6/18/13 quasi
6/18/13 Tucsondrew@me.com
6/18/13 quasi
6/19/13 trj
6/20/13 b92057@yahoo.com
6/20/13 quasi
6/20/13 b92057@yahoo.com
6/22/13 b92057@yahoo.com
6/23/13 quasi
6/25/13 b92057@yahoo.com
6/25/13 quasi
6/25/13 b92057@yahoo.com
6/26/13 quasi
6/26/13 Brian Q. Hutchings
6/27/13 b92057@yahoo.com
6/27/13 quasi
6/27/13 b92057@yahoo.com
6/27/13 quasi
6/27/13 quasi
6/28/13 b92057@yahoo.com
6/28/13 quasi
6/28/13 b92057@yahoo.com
6/29/13 quasi
7/1/13 b92057@yahoo.com
7/2/13 quasi
6/19/13 b92057@yahoo.com
6/19/13 quasi
6/20/13 b92057@yahoo.com
6/20/13 Tucsondrew@me.com
6/21/13 quasi
6/21/13 quasi
6/22/13 b92057@yahoo.com
6/23/13 quasi
6/19/13 b92057@yahoo.com
6/20/13 quasi
6/20/13 quasi
6/20/13 Butch Malahide
6/20/13 Butch Malahide
6/19/13 b92057@yahoo.com
6/20/13 b92057@yahoo.com