2006/06/29 by Carsten Schultz, Schultz, Carsten
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Graph Theory Research #Algebraic Topology (math.AT) #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #math.AT #math.CO
paper · pdf · doi:10.48550/arxiv.math/0606763
arxiv created 2006/06/29 · openalex publication_date 2006/06/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By Lovasz' 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>0. This gives a new and simple proof of the strong form of the graph colouring theorem by Babson and Kozlov, which had been conjectured by Lovasz, 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 Zivaljevic in a previous elegant proof of a special case. We then generalise 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 colouring bound in the theorem by Babson & Kozlov is also never weaker than that from Lovasz' proof of the Kneser conjecture.