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.independent

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 ]
quasi

Posts: 10,232
Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 20, 2013 4:44 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 ...

V = {0,1,2,...,9}

E = {all possible edges {x,y} except those for which
x - y is congruent mod 10 to one of 4,5,6}

Explicitly,

0 is adjacent to 1,2,3,7,8,9
1 is adjacent to 2,3,4,8,9,0
2 is adjacent to 3,4,5,9,0,1
...
9 is adjacent to 0,1,2,6,7,8

Visually, two vertices are adjacent iff their circular distance
mod 10 is at most 3.

It's clear that all vertices of G have degree exactly 6.

Suppose S is a 5-element subset of G such that the restriction
of G to S is isomorphic to K5. Let x,y be distinct elements of
S. If x = y mod 5 then x - y = 5 mod 10, but then x,y would be
non-adjacent in G. Hence no two distinct elements of S are
congruent mod 5. It follows that each of the 5 sets

{0,5}, {1,6}, {2,7}, {3,8}, {4,9}

contains exactly one element of S.

By symmetry, assume 0 is in S.

Then 4,5,6 are not in S.

Since 4 is not in S, 9 must be in S.

Since 6 is not in S, 1 must be in S.

Since 9 is in S, 3,4,5 are not in S.

Since 1 is in S, 5,6,7 are not in S.

Thus, 3,4,5,6,7 are not in S, but that eliminates 5 elements
of V, leaving at most 4 elements for S, contradiction.

It follows that G has no subgraph isomorphic to K5.

Finally, assume G is 4-colorable.

Since vertices 0,1,2,3 are pairwise adjacent, they must have
4 distinct colors c0,c1,c2,c3 say.

But then:

Vertex 4 is adjacent to vertices 1,2,3 so vertex 4 must have
color c0.

Vertex 5 is adjacent to vertices 2,3,4 so vertex 5 must have
color c1.

Vertex 6 is adjacent to vertices 3,4,5 so vertex 6 must have
color c2.

Vertex 7 is adjacent to vertices 4,5,6 so vertex 7 must have
color c3.

Vertex 8 is adjacent to vertices 5,6,7 so vertex 8 must have
color c0.

Vertex 9 is adjacent to vertices 6,7,8 so vertex 9 must have
color c1.

But we also have:

Vertex 9 is adjacent to vertices 0,1,2 so vertex 9 must have
color c3, contradiction, since we've shown that it must have
color c1.

Thus, the graph G yields an example showing that the answer to
the OP's question is no.

quasi


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.