The following is a summary of a talk I have given at the combinatorics workshop in Oberwolfach in January 2006. This work has subsequently grown into the article Graph colourings, spaces of edges and spaces of circuits.

In the proof of Kneser’s Conjecture, Lovász has shown that if the neighbourhood
complex of a graph G is (k - 1)-connected, its chromatic number is at least k+2.
Later formulations of this theorem replace the neighbourhood complex by the
complex Hom(K_{2},G), which is homotopy equivalent to it. One variant of this theorem
is the following.

Theorem 1 [Lov78, BK06a]. Let G be a graph with at least one edge. Then

For graphs H and G, the cell complex Hom(H,G) has the graph homomorphisms
from H to G as 0-cells, while the higher dimensional cells are indexed by
multi-homomorphisms, functions which assign to every vertex of H a non-empty set of
vertices of G such that every choice of one of these for every vertex of H yields a graph
homomorphism. An involution on H which flips an edge makes Hom(H,G) into a free
ℤ_{2}-space. The emphasis on the cohomological index of the ℤ_{2}-action comes from the
work of Babson & Kozlov on the following theorem which proves a conjecture by
Lovász.

Theorem 2 [BK06b, Sch05]. Let G be a graph with an odd cycle and r ≥ 1. Then

Previous proofs of this theorem can be summarized at follows. One studies the
complex Hom(C_{2r+1},K_{n}). This is the hard part. Then the functorality of Hom in the
second argument is used to deduce information on Hom(C_{2r+1},G) from the existence of
an n-colouring of G, i.e. from Hom(G,K_{n})∅.

Extending a surprising and elegant partial proof of Theorem 2 by
Živaljević [Živ05a, Živ05b], we present a simpler way of obtaining the desired
information on Hom(C_{2r+1},K_{n}), or even Hom(C_{2r+1},G) for an arbitrary graph G.
This uses the idea that Hom is not only functorial, but that there is a continuous map
extending composition of homomorphisms, in this case

Using properties of this map and of the ℤ_{2}-actions on Hom(K_{2},C_{2r+1}) induced by
involutions on K_{2} and C_{2r+1} we obtain the following result.

Theorem 3. Let G be a graph with an odd cycle and r ≥ 1. Then

This reduces Theorem 2 to Theorem 1. It therefore proves Theorem 2 in a simple
way, but also shows that lower bounds on the chromatic number that can be obtained
from it can also be obtained from the complex Hom(K_{2},G) originally studied by
Lovász.

Theorem 3 can be generalized as follows.

Theorem 4. Let G,G′ be graphs with involutions, the involution on G flipping an edge, and k ≥ 1. If

- coind
_{ℤ2}Hom(G,G′^{ℤ2}) ≥ k - 1, - there is a graph homomorphism from G to G′ that commutes with the involutions, and
- Hom(G,G′) is (k - 1)-connected,

then

Here, G′^{ℤ2} is a graph whose vertex set is the set of all orbits of the involution on G′.
Its edge set is the largest one such that the map V (G′^{ℤ2}) →(V (G′)) assigning to each
orbit the orbit itself is a multi-homomorphism.

This theorem can be applied to yield a result analogous to Theorem 2, with circuits of chromatic number 3 replaced by Kneser graphs of chromatic number 4.

[BK06a] Babson, E. and Kozlov, D. N. Complexes of graph homomorphisms. Isr. J. Math., 2006. In press, math.CO/0310056.

[BK06b] —. Proof of the Lovász conjecture. Annals of Mathematics, 2006. In press, math.CO/0402395.

[HL05] Hoory, S. and Linial, N. A counterexample to a conjecture of Björner and Lovász on the χ-coloring complex. J. Combinatorial Theory, Ser. B, 95:346–349, 2005.

[Lov78] Lovász, L. Kneser’s conjecture, chromatic number and homotopy. J. Combinatorial Theory, Ser. A, 25:319–324, 1978.

[Sch05] Schultz, C. A short proof of w_{1}^{n}(Hom(C_{2r+1},K_{n+2})) = 0 for all n and a graph
colouring theorem by Babson and Kozlov, 2005. Preprint, 8pp., math.AT/0507346.

[Živ05a] Živaljević, R. T. Parallel transport of Hom-complexes and the Lovász conjecture, 2005. 17 pp., math.CO/0506075.

[Živ05b] —. Combinatorial groupoids, cubical complexes, and the Lovász conjecture, 2005. 28 pp., math.CO/0510204.

Back to my home page.