Date: Jun 20, 2013 4:44 AM
Author: quasi
Subject: Re: A New Graph Coloring Conjecture.

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}


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.