Graph colorings, spaces of edges and spaces of circuits (Q1028347)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph colorings, spaces of edges and spaces of circuits |
scientific article |
Statements
Graph colorings, spaces of edges and spaces of circuits (English)
0 references
30 June 2009
0 references
By \textit{L. Lovasz}' proof of the Kneser conjecture [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)], the chromatic number of a graph \(\Gamma\) is bounded from below by the index of the \(\mathbb Z_n\)-space \(\Hom(K_2,\Gamma)\) plus two, where \(K_2\) denotes the complete graph on two vertices. The author shows that the cohomological index of \(\Hom(K_2,\Gamma)\) is also greater than the cohomological index of the \(\mathbb Z_2\)-space \(\Hom(C_{2r+1},\Gamma)\) for \(r \geq 1\), where \(C_{2r+1}\) denotes the circuit of length \(2r+1\). This gives a new proof of the strong form of the graph colouring theorem by \textit{E. Babson} and \textit{D. N. Kozlov} [Ann. Math. (2) 165, No. 3, 965--1007 (2007; Zbl 1132.05019)] and at the same time shows that it never gives a stronger bound than can be obtained by \(\Hom(K_2,\Gamma)\). The proof given by the author was inspired by work by \textit{R. T. Zivaljevic} [Discrete Comput. Geom. 41, No. 1, 135--161 (2009; Zbl 1232.05242)]. These results are consequences of the main result of the article under review, which is a description of the \(\mathbb Z_2\)-homotopy type of the direct limit of the system of all spaces \(\Hom(C_{2r+1},\Gamma)\) in terms of the \(\mathbb Z_2\)-homotopy type of \(\Hom(K_2,\Gamma)\); cf.\ Theorems 1.5 and 6.6.
0 references
graph homomorphism
0 references
graph colouring
0 references
graph complex
0 references
0 references
0 references