Graph colorings, spaces of edges and spaces of circuits

By Lovász' proof of the Kneser conjecture, the chromatic number of a graph G is bounded from below by the index of the Z2-space Hom(K2,G) plus two. We show that the cohomological index of Hom(K2,G) is also greater than the cohomological index of the Z2-space Hom(C2r+1,G) for r⩾1. This gives a new and simple proof of the strong form of the graph coloring theorem by Babson and Kozlov, which had been conjectured by Lovász, and at the same time shows that it never gives a stronger bound than can be obtained by Hom(K2,G). The proof extends ideas introduced by Živaljević in a previous elegant proof of a special case. We then generalize the arguments and obtain conditions under which corresponding results hold for other graphs in place of C2r+1. This enables us to find an infinite family of test graphs of chromatic number 4 among the Kneser graphs.Our main new result is a description of the Z2-homotopy type of the direct limit of the system of all the spaces Hom(C2r+1,G) in terms of the Z2-homotopy type of Hom(K2,G). A corollary is that the coindex of Hom(K2,G) does not exceed the coindex of Hom(C2r+1,G) by more then one if r is chosen sufficiently large. Thus the graph coloring bound in the theorem by Babson and Kozlov is also never weaker than that from Lovász' proof of the Kneser conjecture.