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

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


Oops -- miscount, it leaves 5 elements for S, not 4, so no
contradiction yet. But the desired contradiction is just one
step away ...

Since 3,4,5,6,7 are eliminated, there are 5 remaining elements,
hence S must be the 5-element set {0,1,2,8,9}. But 2 and 8 are
not adjacent, 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