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