ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 9, Pages 61–68 (August 26, 2003) S 1079-6762(03)00112-4

TOPOLOGICAL OBSTRUCTIONS TO GRAPH COLORINGS

ERIC BABSON AND DMITRY N. KOZLOV

(Communicated by Ronald L. Graham)

Abstract. For any two graphs G and H Lovász has defined a cell complex Hom (G, H) having in mind the general program that the algebraic invariants of these complexes should provide obstructions to graph colorings. Here we announce the proof of a conjecture of Lovász concerning these complexes with G a cycle of odd length. More specifically, we show that

If Hom (C_{2r+1}, G) is k-connected, then χ(G) ≥ k + 4. Our actual statement is somewhat sharper, as we find obstructions already in the nonvanishing of powers of certain Stiefel-Whitney classes.

1. Introduction

One of the central questions of graph theory is to find lower bounds for the number of colors in an admissible coloring of the set of vertices of a graph (a coloring is called admissible if any 2 vertices that are connected by an edge get different colors). The minimal possible number of colors in an admissible coloring is called the chromatic number of the graph, and is denoted by χ(G). In 1978 L. Lovász solved the Kneser conjecture by finding geometric obstructions of Borsuk-Ulam type to graph colorings.

Theorem 1.1 (Kneser-Lovász, [1, 2]). Let Γ_{k,n} be the graph whose vertices are all k-subsets of [n], and edges are all pairs of disjoint k-subsets; here 1 ≤ k ≤ n/2. Then χ(Γ_{k,n}) = n − 2k + 2.

The hard part was to show the inequality χ(Γ_{k,n}) ≥ n − 2k + 2. Lovász’ idea to achieve that was to associate a simplicial complex N (G), called the neighborhood complex, to an arbitrary graph G, and then use the connectivity information of the topological space N (G) to find obstructions to the colorability of G.

To define N (G) we need some notations. For any graph G, let V (G) denote the set of its vertices, and E(G) ⊆ V (G) × V (G) the set of its edges. Since all the graphs in this paper are undirected, (x, y) ∈ E(G) implies (y, x) ∈ E(G). We allow our graphs to contain loops. For a graph G we distinguish between looped and unlooped complements, namely we let ∁G be the graph defined by V (∁G) = V (G), E(∁G) = (V (G) × V (G)) \ E(G), while \overline{G} is the graph defined by

\begin{matrix}c \\ ◯ \end{matrix}2003 American Mathematical Society

Received by the editors May 17, 2003.

2000 Mathematics Subject Classification. Primary 05C15; Secondary 57M15, 55N91, 55T99.

Key words and phrases. Graphs, chromatic number, graph homomorphisms, Stiefel-Whitney classes, equivariant cohomology, free action, spectral sequences, obstructions, Kneser conjecture, Borsuk-Ulam theorem.

V (\overline{G}) = V (G), E(\overline{G}) = E(∁G) \ \{(v, v) | v ∈ V (G)\}. For a graph G and S ⊆ V (G) we denote by G[S] the graph on the vertex set S induced by G, that is V (G[S]) = S, E(G[S]) = (S × S) ∩ E(G).

The complex N (G) can then be defined by taking as its vertices all nonisolated vertices of G, and as its simplices all the subsets of V (G) which have a common neighbor; in other words, the maximal simplices of N (G) are N (v), for v ∈ V (G), where N (v) = {w ∈ V (G) | (v, w) ∈ E(G)} is the set of all neighbors of v.

Theorem 1.2 (Lovász, [2]). Let G be a graph without loops, such that N (G) is k-connected; then χ(G) ≥ k + 3.

Numerous papers followed Lovász’ pioneering work; see [4] for a good recent survey. Generalizing the original line of thought, for any pair of graphs G and H, Lovász has defined a cell complex Hom (G, H).

Recall that a graph homomorphism is a map ϕ : V (G) → V (H) such that ϕ × ϕ : E(G) → E(H), that is, if x, y ∈ V (G) are connected by an edge, then ϕ(x) and ϕ(y) are also connected by an edge. We denote the set of all homomorphisms from G to H by Hom(G, H).

Definition 1.3. Hom (G, H) is a polyhedral complex whose cells are indexed by all functions η : V (G) → 2^{V (H)} \ {∅} such that if (x, y) ∈ E(G), for any x̃ ∈ η(x) and ỹ ∈ η(y) we have (x̃, ỹ) ∈ E(H).

The closure of a cell η consists of all cells indexed by η̃ : V (G) → 2^{V (H)} \ {∅}, which satisfy η̃(v) ⊆ η(v), for all v ∈ V (G).

In particular, the set of vertices of Hom (G, H) is precisely Hom(G, H).

As Proposition 2.1 shows, already the complexes Hom (K_{2}, G) contain the homotopy type information of the neighbourhood complexes. This observation makes one try to look for obstructions coming from maps from other graphs than K_{2}.

In this paper we announce the proof of the following conjecture of Lovász, which is a natural next step, after Theorem 1.2, in the general program of finding topological obstructions to the existence of the graph homomorphisms.

Theorem 1.4. Let G be a graph, and let r, k ∈ ℤ, such that r ≥ 1, k ≥ −1. If Hom (C_{2r+1}, G) is k-connected, then χ(G) ≥ k + 4.

Here, C_{2r+1} is a (2r + 1) cycle, i.e., a graph defined by V (C_{2r+1}) = ℤ/(2r + 1)ℤ,

E(C_{2r+1}) = {([x], [x + 1]), ([x + 1], [x]) | x ∈ ℤ/(2r + 1)ℤ} .

To state our main result we need more notations. Let X be a CW complex with a free ℤ_{2}-action. By the general theory of principal bundles, there exists a ℤ_{2}- equivariant map w̃ : X → S^{∞}, where ℤ_{2} acts on S^{∞} by the antipodal map, and the induced map w : X/ℤ_{2} → ℝℙ^{∞} is unique up to homotopy. This in turn induces a canonical algebra homomorphism w^{∗} : H^{∗}(ℝℙ^{∞}; ℤ_{2}) → H^{∗}(X/ℤ_{2}; ℤ_{2}). Let z ∈ H^{1}(ℝℙ^{∞}; ℤ_{2}) denote the nontrivial cohomology class; then H^{∗}(ℝℙ^{∞}; ℤ_{2}) ≃ ℤ_{2}[z] as graded algebras. We denote w^{∗}(z) ∈ H^{1}(X/ℤ_{2}; ℤ_{2}) by ϖ_{1}(X), and call it the first Stiefel-Whitney class of the ℤ_{2}-space X. Clearly, ϖ_{1}^{k}(X) = w^{∗}(z^{k}).

Let ℤ_{2} act on C_{2r+1} by mapping [x] ∈ ℤ/(2r + 1)ℤ to [−x], and let γ ∈ Hom(C_{2r+1}, C_{2r+1}) denote the corresponding graph homomorphism. Furthermore, let ℤ_{2} act on K_{m} for m ≥ 2, by swapping the vertices 1 and 2 and fixing the vertices 3, …, m; here, K_{m} is the graph defined by V (K_{m}) = [m], E(K_{m}) = {(x, y) | x, y ∈ [m], x ≠ y}. These induce free ℤ_{2}-actions on Hom (C_{2r+1}, G) and Hom (K_{m}, G).

Theorem 1.5. Let G be a graph.

(a) If ϖ_{1}^{k}(Hom (C_{2r+1}, G)) ≠ 0, then χ(G) ≥ k + 3.

(b) If ϖ_{1}^{k}(Hom (K_{m}, G)) ≠ 0, then χ(G) ≥ k + m.

Since we know that for a k-connected space X with a free ℤ_{2}-action ϖ_{1}^{k+1}(X) ≠ 0, Theorem 1.5 implies Theorem 1.4 as well as the following corollary.

Corollary 1.6. Let G be a graph, and let m, k ∈ ℤ, such that m ≥ 2, k ≥ −1. If Hom (K_{m}, G) is k-connected, then χ(G) ≥ k + m + 1.

Acknowledgments. We would like to thank László Lovász and Péter Csorba for insightful discussions. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation, and the University of Bern.

2. Homotopy type of the Hom complexes

First, we remark two properties of the Hom complexes:

(1) Cells of Hom (G, H) are direct products of simplices. More specifically, each η as in Definition 1.3 is a product of |V (G)| simplices, having dimensions |η(x)| − 1, for x ∈ V (G).

(2) Hom (H, −) is a covariant, while Hom (−, H) is a contravariant functor from Graphs to Top, where Graphs is a category having graphs as objects, and graph homomorphisms as morphisms. If ϕ ∈ Hom(G, G′), then we shall denote the induced topological maps as ϕ^{H} : Hom (H, G) → Hom (H, G′) and ϕ_{H} : Hom (G′, H) → Hom (G, H).

Proposition 2.1. Hom (K_{2}, G) is homotopy equivalent to N (G).

If Proposition 2.1 coupled with Theorem 1.2 were to be interpreted as that the obstructions to colorability found by Lovász in 1978 stem from the graph K_{2}, then the idea behind the Lovász Conjecture could be thought of as that the next natural class of obstructions should come from the odd cycles, C_{2r+1}.

The next proposition is the crucial step in the proof of Theorem 1.5(b).

Proposition 2.2. Hom (K_{m}, K_{n}) is homotopy equivalent to a wedge of (n − m)- dimensional spheres.

Next, we need a technical Quillen-type lemma. For any small category C (in particular a finite poset) we denote by Δ(C) the realization of the nerve of that category. For any finite poset P, we let P^{op} denote the finite poset which has the same set of elements as P, but the opposite partial order. Also, for any finite poset P, whenever the subset of the elements of P is regarded as a poset, the partial order is taken to be induced from P.

Proposition 2.3. Let ϕ : P → Q be a map of finite posets. Consider a list of possible conditions on ϕ. Condition (A). For every q ∈ Q, Δ(ϕ^{−1}(q)) is contractible. Condition (B). For every p ∈ P and q ∈ Q with ϕ(p) ≥ q the poset ϕ^{−1}(q) ∩ P_{≤p} has a maximal element. Condition (B^{op}). Let ϕ^{op} : P^{op} → Q^{op} be the poset map induced by ϕ. We require that ϕ^{op} satisfies Condition (B).

Then (1) If ϕ satisfies (A) and either (B) or (B^{op}), then ϕ is a homotopy equivalence.

(2) If ϕ satisfies (B) and (B^{op}), and Q is connected, then for any q, q′ ∈ Q we have Δ(ϕ^{−1}(q)) ≃ Δ(ϕ^{−1}(q′)). Furthermore, we have a fibration homotopy long exact sequence:

(2.1)  … ⟶ π_{i}(Δ(ϕ^{−1}(q))) ⟶ π_{i}(Δ(P)) ⟶ π_{i}(Δ(Q)) ⟶ ….

Proof. The argument is based on using Quillen’s Theorems A and B (see [3, pp. 85, 89]) for the induced map Bd ϕ : Bd P → Bd Q, where Bd denotes the barycentric subdivision, that is the poset of all the chains in the given poset. The details will appear elsewhere. □

Proposition 2.4. If G and H are graphs and u and v are vertices of G such that N(v) ⊆ N(u), then i : G − v ↪ G induces a homotopy equivalence i_{H} : Hom (G, H) → Hom (G − v, H).

Proof. It suffices to apply proposition 2.3(1) to the cellular map i_{H} : Hom (G, H) → Hom (G − v, H), which forgets the colors of v. □

Corollary 2.5. If T is a tree with at least one edge, then the map i_{K_{n}}: Hom (T, K_{n})→ Hom (K_{2}, K_{n}) induced by any inclusion i : K_{2} ↪ T is a homotopy equivalence. Furthermore, if F is a forest, then Hom (\overline{F} , K_{n}) ≃ Hom (K_{m}, K_{n}), where m is the maximal cardinality of an independent set in F.

3. Hom_{+} and filtrations

For a finite graph H, let H_{+} be the graph obtained from H by adding an extra vertex, called the base vertex, and connecting it by edges to all the vertices of H_{+} including itself.

Definition 3.1. Let G and H be two graphs. The simplicial complex Hom_{+} (G, H) is defined to be the link in Hom (G, H_{+}) of the homomorphism that maps every vertex of G to the base vertex in H_{+}.

So Hom_{+} (G, H) is just like Hom (G, H) with the difference that we also allow empty lists of colors, i.e., the cells are functions η : V (G) → 2^{V (H)}, which also makes it simplicial. We remark that Hom_{+} (H, −) is a covariant functor from Graphs to Top.

Proposition 3.2. Hom_{+} (G, H) is isomorphic to the independence complex of G × ∁H. In particular, Hom_{+} (G, K_{n}) is isomorphic to Ind (G)^{∗n}, where ∗ denotes the simplicial join.

The chain complex of Hom_{+} (G, K_{n}) has a natural filtration. For each simplex of Hom_{+} (G, K_{n}), η : V (G) → 2^{V (K_{n})}, define the support of η to be supp η = V (G) \ η^{−1}(∅). In fact, the same definition for supp holds for any Hom_{+} (G, H). One concise way to phrase it is to simply consider the map t^{G} : Hom_{+} (G, H) → Hom_{+} (G, ∁K_{1}) ≃ Δ_{|V (G)|−1} induced by the homomorphism t : H → ∁K_{1}.

We can now filter C_{∗}(Hom_{+} (G, K_{n})) by the cardinalities of the support. Namely,

F_{−1} = 0, F_{0} = ⟨|supp η| = 1⟩, …, F_{k} = ⟨|supp η| ≤ k + 1⟩, …,

that is F_{k} is the chain subcomplex of C_{∗}(Hom_{+} (G, K_{n})) generated by all simplices whose support set has cardinality at most k + 1.

Clearly, for any k,

F_{k}/F_{k−1} = C_{∗}( ∐_{S⊆V (G),|S|=k+1} Hom (G[S], K_{n}))[k],

where the brackets [−] denote shifting. In particular, F_{|V (G)|−1} = C_{∗}(Hom_{+} (G, K_{n})), and F_{|V (G)|−1}/F_{|V (G)|−2} = C_{∗}(Hom (G, K_{n}))[|V (G)| − 1].

Next, we describe a natural filtration on C_{∗}(Hom_{+} (C_{2r+1}, K_{n})/ℤ_{2}; ℤ). Let c, a_{1}, …, a_{r}, b_{1}, …, b_{r} denote the vertices of C_{2r+1} so that γ(a_{i}) = b_{i}, for any i ∈ [r], and (c, a_{1}), (a_{i}, a_{i+1}) ∈ E(C_{2r+1}), for any i ∈ [r − 1]. Identify V (C_{2r+1}) with the vertices of an abstract simplex Δ_{2r} of dimension 2r. We subdivide Δ_{2r} by adding r more vertices, denoted c_{1}, c_{2}, …, c_{r}, and defining a new abstract simplicial complex Δ̃_{2r} on the set {c, a_{1}, …, a_{r}, b_{1}, …, b_{r}, c_{1}, …, c_{r}} = V (Δ̃_{2r}). The simplices of Δ̃_{2r} are all the subsets of V (Δ̃_{2r}) which do not contain the subset {a_{i}, b_{i}}, for any i ∈ [r].

One can think of this new complex Δ̃_{2r} as the one obtained from Δ_{2r} by representing it as a join {c}∗[a_{1}, b_{1}]∗⋯∗[a_{r}, b_{r}], inserting one additional vertex into the middle of each [a_{i}, b_{i}], and then taking the join of {c} and the subdivided intervals. For σ̃ ∈ Δ̃_{2r} we define ϑ(σ̃) ∈ Δ_{2r} by ϑ(σ̃) = (σ̃ \ {c_{1}, …, c_{r}}) ∪ ⋃_{c_{i}∈σ̃}{a_{i}, b_{i}}.

Δ̃_{2r} has an additional property: if a simplex of Δ̃_{2r} is γ-invariant, then it is fixed pointwise. This allows us to introduce a simplicial structure on Δ̃_{2r}/ℤ_{2} by taking the orbits of the simplices of Δ̃_{2r} as the simplices of Δ̃_{2r}/ℤ_{2}.

Let us now describe a chain complex C̃_{∗}(Hom_{+} (C_{2r+1}, K_{n})), which comes from a different triangulation of the topological space Hom_{+} (C_{2r+1}, K_{n}). The chain complex consists of vector spaces over ℤ_{2}. The generators are pairs (η, σ), where η ∈ Hom_{+} (C_{2r+1}, K_{n}), and σ ∈ Δ̃_{2r}, such that ϑ(σ) = supp η. Such a pair corresponds to the cell η ∩ supp^{−1}(σ). The codimension 1 boundary of (η, σ) is the sum of the following generators:

(1) (η̃, σ), if supp η̃ = supp η, and η̃ ∈ ∂ η;

(2) (η, σ̃), if σ̃ ∈ ∂ σ, and ϑ(σ) = ϑ(σ̃);

(3) (η̃, σ \{x}), if x ∈ V (Δ̃_{2r}), Y = ϑ({x})\ϑ(σ \{x}) ≠ ∅, where η̃ is obtained from η by setting η to be ∅ on the vertex set η^{−1}(Y), and where we require that all the values of η|_{η^{−1}(Y)} have cardinality 1.

Here ∂ denotes the codimension 1 boundary. The degree of (η, σ) in

C̃_{∗}(Hom_{+} (C_{2r+1}, K_{n}))

is given by

deg(η, σ) = |σ| − 1 + ∑_{v∈V (C_{2r+1}), |η(v)|≠0}(|η(v)| − 1) = deg η + |σ| − |ϑ(σ)|.

ℤ_{2} acts on C̃_{∗}(Hom_{+} (C_{2r+1}, K_{n})) and we let C̃_{∗}^{ℤ_{2}}(Hom_{+} (C_{2r+1}, K_{n})) denote its subcomplex consisting of the invariant chains. By construction of the subdivision, C̃_{∗}^{ℤ_{2}}(Hom_{+} (C_{2r+1}, K_{n})) is a chain complex for a triangulation of the space Hom_{+} (C_{2r+1}, K_{n})/ℤ_{2}.

Just like before, we consider the natural filtration (F̃_{−1} ⊆ F̃_{0} ⊆ …) on the chain complex C̃_{∗}^{ℤ_{2}}(Hom_{+} (C_{2r+1}, K_{n})) by the cardinality of σ. This time, for any k

F̃_{k}/F̃_{k−1} = C_{∗}(∐_{σ}(Hom (G[ϑ(σ)], K_{n})/ℤ_{2}) ∐_{τ} Hom (G[ϑ(τ)], K_{n}))[k],

where the first coproduct is taken over all σ ∈ Δ̃_{2r} which are ℤ_{2}-invariant, and the second coproduct is taken over all τ ∈ Δ̃_{2r} which are not ℤ_{2}-invariant. In addition |σ| = |τ| = k + 1 is required.

4. The spectral sequences and the proof of the Lovász Conjecture

We shall show that

(4.1)  (ι̃_{K_{n}})_{n−2} : H_{n−2}(Hom (C_{2r+1}, K_{n})/ℤ_{2}) → H_{n−2}(Hom (K_{2}, K_{n})/ℤ_{2})

is a 0-map, where the homology is taken with coefficients in ℤ_{2}. Here ι : K_{2} ↪ C_{2r+1} is either of the two ℤ_{2}-equivariant inclusion maps which take the vertices of K_{2} to {a_{r}, b_{r}}. It induces a ℤ_{2}-equivariant map ι_{K_{n}} : Hom (C_{2r+1}, K_{n}) → Hom (K_{2}, K_{n}), and hence also the quotient map

ι̃_{K_{n}} : Hom (C_{2r+1}, K_{n})/ℤ_{2} → Hom (K_{2}, K_{n})/ℤ_{2} .

Note that if (ι̃_{K_{n}})_{n−2} is a 0-map, then so is

(ι̃_{K_{n}})^{n−2} : H^{n−2}(Hom (K_{2}, K_{n})/ℤ_{2}; ℤ_{2}) → H^{n−2}(Hom (C_{2r+1}, K_{n})/ℤ_{2}; ℤ_{2}),

since we are working over a field. By the functoriality of the Stiefel-Whitney classes, this implies that ϖ_{1}^{n−2}(Hom (C_{2r+1}, K_{n})) = 0, which is a crucial fact for our proof of Lovász Conjecture. We shall sketch the full computation for the case of n odd. For even n the Lovász Conjecture follows already from (4.2); see the discussion following (4.2).

The E^{1}-tableau of the first spectral sequence is given by E_{d,s}^{1} = H_{d}(F_{s}, F_{s−1}). From our remarks concerning this filtration it follows that each E_{d,s}^{1} is a direct sum of the appropriate homology groups of Hom (H, K_{n}), where H is a subgraph of C_{2r+1}. Since all proper subgraphs of C_{2r+1} are forests, we know the first tableau, except for the (2r)th row, by Corollary 2.5. It can be shown (we omit the technical details) that the only part of the spectral sequence which is relevant for the computation of the homology groups of Hom (C_{2r+1}, K_{n}) up to dimension n − 2, consists of two chain complexes:

D_{∗}^{0} : E_{0,0}^{1} → E_{1,1}^{1} → E_{2,2}^{1} → … → E_{2r−1,2r−1}^{1}

and

D_{∗}^{1} : E_{n−2,0}^{1} → E_{n−1,1}^{1} → E_{n,2}^{1} → … → E_{n−2+2r−1,2r−1}^{1},

where all the differentials are d^{1} from the spectral sequence. To start with, D_{∗}^{0} is isomorphic to the chain complex of the (2r − 1)-skeleton of the (2r)-simplex Δ_{2r}, thus having only the homology in dimensions 0 and 2r − 1. We can conclude that E_{0,0}^{2} = ℤ, while E_{1,1}^{2} = E_{2,2}^{2} = ⋯ = E_{2r,2r}^{2} = 0, hence E_{2r,2r}^{1} = ℤ.

The analysis of D_{∗}^{1} is a little more interesting. By taking the induced subgraphs, we identify subsets of V (C_{2r+1}) with collections of arcs on a circle (some arcs of length 1), such that every two arcs are separated by at least one vertex. The detailed analysis using Corollary 2.5 shows that the generators of the vector spaces in D_{∗}^{1} can be indexed with pairs (S, A), where S ⊆ V (C_{2r+1}), and A a connected component of C_{2r+1}[S] with at least one edge. We call such components arcs, and we call this specific A a marked arc. The dimension of (S, A) is |S|. The boundary of (S, A) is the sum (with appropriate signs) over all pairs obtained by deleting an element of S. One can work out that, if the deleted element is not in A, then the arc remains the same, while a deleted element which is in A contributes to the boundary a sum of two pairs, depending on which piece of A is taken as a new arc, where the pieces of length 1 give 0 contribution.

We can now filter D_{∗}^{1} by the length of the marked arc A. By the previous argument, the relative chain complexes will split into subcomplexes each corresponding to a particular marked arc. All these subcomplexes are acyclic (they are reduced chain complexes of simplices) except for two, namely, those corresponding to S = V (C_{2r+1}) \ {c} and S = V (C_{2r+1}) \ {a_{r}, b_{r}}.

The complete computation of the first differential shows that

(4.2)  H_{i}(Hom (C_{2r+1}, K_{n}); ℤ_{2}) = \begin{cases}ℤ_{2}, & if i = 0, n − 3, n − 2, \\ 0, & if 1 ≤ i ≤ n − 4. \end{cases}

Additionally, one can see that H_{i}(Hom (C_{2r+1}, K_{n}); ℤ) = 0, for 1 ≤ i ≤ n − 4, and H_{n−2}(Hom (C_{2r+1}, K_{n}); ℤ) = H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ) = ℤ, for n odd, while H_{n−2}(Hom (C_{2r+1}, K_{n}); ℤ) = 0, H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ) = ℤ_{2}, for n even.

We remark that from this computation Lovász Conjecture follows easily in the case of n even. The essence is to show that there is no ℤ_{2}-map of S^{n−2} into Hom (C_{2r+1}, K_{n}). If this map existed, then, combined with the canonical map Hom (C_{2r+1}, K_{n}) → Hom (K_{2}, K_{n}), induced by K_{2} ↪ C_{2r+1}, it would yield a ℤ_{2}- map of degree 0 of S^{n−2} into itself, which is impossible.

We assume for the rest of the paper that n is odd. In this case one can show that the ℤ_{2}-action on H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ) is always multiplication by −1.

The E^{1}-tableau of the second spectral sequence is given by E_{d,s}^{1} = H_{d}(F̃_{s}, F̃_{s−1}). This time each E_{d,s}^{1} splits as a vector space over ℤ_{2} into direct sums of

H_{i}(Hom (H, K_{n}); ℤ_{2}) ,

where H is an induced subgraph of C_{2r+1}, and of Hom (H, K_{n})/ℤ_{2}, where H is a ℤ_{2}- invariant induced subgraph of C_{2r+1}. The detailed analysis of the first tableau of this spectral sequence is rather technical and will appear elsewhere. We sketch here the basic steps of the argument.

(1) We single out the generator ρ in E_{n−2+r,r}^{1} which is the contribution of {c, c_{1}, …, c_{r}}. Let Ẽ_{n−2+r,r}^{1} denote the part of E_{n−2+r,r}^{1} which is spanned by the rest of the generators.

(2) Analysis of the boundary of ρ shows that if (ι̃_{K_{n}})_{n−2} is not a 0-map, then the rank of d^{1} : E_{n−2+r,r}^{1} → E_{n−3+r,r−1}^{1} is one higher than the rank of d̃^{1} : Ẽ_{n−2+r,r}^{1} → E_{n−3+r,r−1}^{1}. This is because the boundary of other generators of E_{n−2+r,r}^{1} does not contain the generator in E_{n−3+r,r−1}^{1} indexed by {c_{1}, …, c_{r}}. Indeed, the only place for it to be would be in the boundary of the generators indexed by {x, c_{1}, …, c_{r}}, where x = a_{i} or x = b_{i}, but omitting x is a double covering map, which is a 0-map on the ℤ_{2}-homology.

(3) The differential d^{1} : E_{n−2+r,r+1}^{1} → E_{n−3+r,r}^{1} is a 0-map, because q_{n−3} in (4.3) below is a 0-map.

(4) The chain complex

E_{n−2+r,r+1}^{1} → E_{n−1+r,r+2}^{1} → … → E_{n−3+2r,2r}^{1}

is a chain complex of ℝℙ^{r−1} over ℤ_{2}. Hence E_{n−2+r,r+1}^{2} = ℤ_{2}, and so d^{2} : E_{n−2+r,r+1}^{2} → E_{n−3+r,r−1}^{2} has rank 1.

(5) By means of technical computations we can show that the sequence

E_{n−4+r,r−2}^{1} → E_{n−3+r,r−1}^{1} → Ẽ_{n−2+r,r}^{1}

has homology ℤ_{2} in the middle term. Altogether, this shows equation (4.1). It remains to see that

(4.3)  q_{n−3} : H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ_{2}) → H_{n−3}(Hom (C_{2r+1}, K_{n})/ℤ_{2}; ℤ_{2})

is a 0-map.

Proof of (4.3). First let us see (4.3) over integers. Take

ζ ∈ H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ) .

By our previous computations γ^{K_{n}}(ζ) = −ζ, this means that q_{n−3}(γ^{K_{n}}(ζ)) = −q_{n−3}(ζ). On the other hand, q_{n−3} commutes with the ℤ_{2}-action, that is

q_{n−3}(γ^{K_{n}}(ζ)) = q_{n−3}(ζ) ,

which yields q_{n−3}(ζ) = 0.

Second, by the universal coefficient theorem the map

τ : H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ) ⊗ ℤ_{2} → H_{n−3}(C_{∗}(Hom (C_{2r+1}, K_{n}); ℤ) ⊗ ℤ_{2})

is injective and functorial. In our concrete situation, this map is also surjective, hence the claim follows from the following diagram:

H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ) ⊗ ℤ_{2} ⟶^{0-map} H_{n−3}(Hom (C_{2r+1}, K_{n})/ℤ_{2}; ℤ) ⊗ ℤ_{2}
τ↓^{iso}  ↓
H_{n−3}(Hom (C_{2r+1}, K_{n}); ℤ_{2}) ⟶^{q_{n−3}} H_{n−3}(Hom (C_{2r+1}, K_{n})/ℤ_{2}; ℤ_{2}) □

Proof of the Lovász Conjecture. If the graph G is (k + 3)-colorable, then there exists a homomorphism ϕ : G → K_{k+3}. It induces a ℤ_{2}-equivariant map ϕ^{C_{2r+1}} : Hom (C_{2r+1}, G) → Hom (C_{2r+1}, K_{k+3}). Since the Stiefel-Whitney classes are functorial and ϖ_{1}^{k+1}(Hom (C_{2r+1}, K_{k+3})) = 0, the existence of the map ϕ^{C_{2r+1}} implies that ϖ_{1}^{k+1}(Hom (C_{2r+1}, G)) = 0, which is a contradiction to the assumption of the theorem. □

References

[1] M. Kneser, Aufgabe 300, Jber. Deutsch. Math.-Verein. 58 (1955).

[2] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 81g:05059

[3] D. Quillen, Higher algebraic K-theory I, Lecture Notes in Math., vol. 341, Springer-Verlag, 1973, pp. 77–139. MR 49:2895

[4] G. M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), 671–691. MR 2003d:05088

Department of Mathematics, University of Washington, Seattle, Washington

   E-mail address: babson@math.washington.edu

Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden

   E-mail address: kozlov@math.kth.se

Current address: Department of Mathematics, University of Bern, Switzerland

   E-mail address: kozlov@math-stat.unibe.ch