Carsten Schultz

The relative strength of topological graph colouring obstructions

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.

Extended abstract

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(K2,G), which is homotopy equivalent to it. One variant of this theorem is the following.

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

cohom-indℤ2 Hom(K2, G) ≤ χ(G)- 2.

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 [BK06bSch05]. Let G be a graph with an odd cycle and r 1. Then

cohom -indℤ2 Hom(C2r+1, G) ≤ χ(G)- 3.

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

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(C2r+1,Kn), or even Hom(C2r+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

Hom(K  ,C    )× Hom(C     ,G) → Hom(K   ,G).
       2  2r+1          2r+1             2

Using properties of this map and of the 2-actions on Hom(K2,C2r+1) induced by involutions on K2 and C2r+1 we obtain the following result.

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

cohom-indℤ2 Hom(C2r+1, G)+ 1 ≤ cohom -indℤ2 Hom(K2, G).

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(K2,G) originally studied by Lovász.

Theorem 3 can be generalized as follows.

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


cohom-ind   Hom(G ′,H)+ k ≤ cohom-ind   Hom(G, H)
         ℤ2                          ℤ2
for all graphs H with Hom(G,H)⁄=.

Here, G2 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 (G2) P(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 w1n(Hom(C2r+1,Kn+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.