### Colorings of Graphs

#### Posted by Urs Schreiber

Just heard a talk by Dmitry Kozlov on *combinatorial algebraic topology*, concerned mainly with the problem of coloring graphs.

I didn’t fully understand many of the points and unfortunately I didn’t have the chance of asking the speaker about more details afterwards. Hence this here is not a report of the talk, but rather a vague mentioning of some aspects and a couple of questions. It feels like much of what Kozlov had to say would be of quite some interest to an $n$-categorical audience, if maybe just because there might be room to make that $n$-categorical structure more explicit.

The main point is this:

given a graph $G$, we are looking for colorings of its vertices such that no two vertices connected by an edge have the same color. What is the minimum number of colors, the *chromatic number*
$\chi(G)
\,,$
such that such a coloring exists?

If the graph is the dual of a triangulation drawn on a plane, the answer is given by the famous four color theorem to be
$\chi(G) = 4
\,.$
The proof of that is not easy and in particular not elegant. This is symptomatic for the coloring problem more generally: exact answers are hard to come by. What one aims for instead are good *estimates*, lower bounds in particular, of $\chi(G)$.

One nice way to reformulate the problem of graph colorings, which all of Kozlov’s machinery is based on, amounts to realizing that a consistent (i.e. no equal-colored neighbours) coloring of a graph $G$ with $n$-colors is the same as a graph morphism $c : G \to \mathrm{Codisc}(n) \,.$ Here $\mathrm{Codisc}(n)$ is what graph theorists apparently call the “complete” graph on $n$ vertices, which here I call the codiscrete graph on $n$ vertices: it has precisely one edge from each of its vertices to every other.

A morphism of graphs is much like a functor of the corresponding categories, but with the important constraint that every edge has to go to an edge: as opposed to the categories generated from them, the graphs have no “identity edges”. (And, by the way, I think Kozlov assumes throughout all graphs to be oriented, to have at most one edge for every ordered pair of vertices, and to have no edges from a vertex to itself.)

This is what makes the above reformulation possible: a morphism from a graph $G$ to a codiscrete graph $\mathrm{Codsic}(n)$ will label each vertex of $G$ with one of the $n$ colors, and cannot assign the same color to two neighbouring vertices.

So then, the next step is to get a handle on the Hom-spaces $\mathrm{Hom}_{\mathrm{Graph}}(G,\mathrm{Codisc}(n))$ in the category of graphs.

The crucial point of Kozlov’s work is that he realizes these Hom spaces as *simplicial complexes*. I don’t quite understand the precise definition in detail yet. You can find it for instance as definition 2.1.5 on p. 11 of

Dmitry N. Kozlov
*Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes*

arXiv:math/0505563v2.

So this looks like we are secretly talking about an $\infty$-category of graphs now, or something like this. I don’t know.

The point is that using these simplicial complexes, the space of all possible graph colorings becomes more accessible. Kozlov proves powerful theorems using these complexes, in particular the **Lovász conjecture**:

For a graph $G$, such that the complex $\mathrm{Hom}(C_{2r+1},G)$ is $k$-connected for some integers $r\gt 0$ and $k \gt -2$, we have $\chi(G) \gt k+3 \,.$

(Here $C_n$ is the graph corresponding to the $n$-gon.)

The general strategy is to map these simplicial complexes functorially to topological spaces, and then use known obstruction theory of these spaces to determine if $\mathrm{Hom}(G,T)$ can be nontrivial at all.

In this context I was quite intrigued by what Kozlov said about *spin structures*. As described in section 3 of the above paper, there is a way to use the theory of Stiefel-Whitney characteristic classes to study the Hom-complexes of graphs. That sounds fascinating, since it seems to indicate a relation of the abstract coloring problem – which has the appearance of being “of academic interest” only (if you know what I mean) – to interesting geometric and maybe even physical questions. I’d like to better understand this.

But not right now. I need to call it a day.

Posted at June 26, 2007 9:38 PM UTC
## Re: Colorings of Graphs

This work seems to point to a bridge between the two cultures of mathematics. To see MacLane’s name appearing under Lovász’s in the bibliography of the paper by Koslov you mention is a sign.