quasi
Posts:
10,208
Registered:
7/15/05


Re: A New Graph Coloring Conjecture.
Posted:
Jun 20, 2013 4:44 AM


bill wrote: >bill wrote: >> >> Conjecture: A graph is fourcolorable, 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 4colorable?
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 5element 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 nonadjacent 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 4colorable.
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

