Algebra Universalis, 7 (1977) 313-314 Birkhiiuser Verlag, Basel Colouring lattices BI~LA BOLLOB,~S Given a partially ordered set P, define a graph G(P), called the covering graph of P, as follows. The vertex set of G(P) is P and x, y e P are joined by an edge if one is an immediate successor of the other, i.e. either x < y and there is no z ~ P with xz>y. It is known [2] that for every k there is a partially ordered set P whose covering graph G(P) is at least k-chromatic. On the other hand the graphs of all known lattices seem to be 3-colourable and this prompted Burmeister and Rival [1] to conjecture that the graph of a lattice is always 3-colourable. The aim of this note is to show that the situation is rather different. THEOREM. Given a natural number k there is a lattice L whose covering graph G(L) is not k-colourable. Proof. Let H be a (k + 1)-chromatic graph whose girth, g(H), is greater than 4k, i.e. which does not contain a cycle of length at most 4k. The existence of such a graph was first proved by Erd6s [3]. Let Vt, V2 . . . . . Vk+l be the colour classes of H. Define a partial order on V= U~ +~ v~ as follows. Put x < y if there is a path Xo, xl, x2 . . . . , x, in H such that x = x, y = x, and there is an index i such that x i ~ V~+i, ] = 0, 1 . . . . . I. Suppose xl, x2~ V and Yb Y2~ V are minimal elements greater than both xl and x2. Then for each of the four pairs (xi, yi), i, j = 1, 2, there is a path of length at most k joining x, to Yi. Some sections of these paths form a cycle of length at most 4k, contradicting g(H)>4k. This shows that for any two elements of V there is at most one minimal element greater than both of them and, analogously, there is at most one maximal element less than both of them. Add two elements to V, say 0 and 1. Define 0 < x < 1 for every x ~ V. With these ordering relations VU {0, 1} is easily seen to be a lattice, say L, and the graph of this lattice, G(L), contains H as a subgraph. Since H is not k-colourable, G(L) is not k-colourable either, In the proof above it was entirely trivial to imbed H into the graph of a lattice. Presented by R. P. Dilworth. Received June 17, 1976. Accepted for publication in final form September 16, 1976. 313 314 Bt~LA BOLLOB~.S This prompts the following problems which seem to be considerably harder than the one just solved in this note, Is there a natural number g such that if H is a graph with g (H) - g then H is isomorphic to a subgraph of the graph of a lattice? Provided the answer is negative to this question, one can weaken it by replacing the lattice by a partially ordered set. I believe it isn't even known that g = 6 does not have the required properties. However, probabilistic considerations make me conjecture that the answer is negative even to the second question. To conclude this note I reformulate this conjecture in graph theoretic terms. If G is a graph and < is a total order on the vertex set of G then call a cycle C of G canonical (with respect to g such that taking any total order of the vertex set of H the graph H contains a canonical cycle. The proof of the theorem shows that a graph H having the properties required by this conjecture is not [g/4]-colourable. This means that for a large value of g we shall almost certainly have to use probabilistic arguments to prove the existence of a graph H. REFERENCES [1] P. BURMEISTER and I. RIVAL, A conjecture concerning the coloring of lattices, Proc. of the Conf. on Lattice Theory in Szeged, to appear. [2] B. DESCARTES, A three colour problem, Eureka, April 1947. Solution March 1948. [3] P. ERD6S, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38. University of Cambridge Cambridge England and University o[ Calgary Calgary, Alberta Canada