Search All of the Math Forum:

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

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

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Butch Malahide Posts: 894 Registered: 6/29/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 20, 2013 4:17 PM
 Plain Text Reply

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.

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

© The Math Forum at NCTM 1994-2016. All Rights Reserved.