Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Butch Malahide

Posts: 894
Registered: 6/29/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 20, 2013 4:31 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
Read A New Graph Coloring Conjecture.
b92057@yahoo.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
trj
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/25/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/26/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/26/13
Read Re: A New Graph Coloring Conjecture.
Brian Q. Hutchings
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/28/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/29/13
Read Re: A New Graph Coloring Conjecture.
quasi
7/1/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
7/2/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/19/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.