quasi
Posts:
12,012
Registered:
7/15/05


Re: A New Graph Coloring Conjecture.
Posted:
Jun 20, 2013 5:30 AM


quasi wrote: >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.
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 5element 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 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

