Graphs and Homomorphisms. By Pavol Hell and Jaroslav Nešetřil. Oxford Graduate Texts in Mathematics, Oxford University Press, 2026, Hardcover, Pp. 362, price GBP 127.00. Hardcover: ISBN 9780198708704.

A first version of this book was published in `Oxford Lecture Series in Mathematics and its Applications' in 2004, addressing the main themes related to the subject throughout six chapters. This second edition updates the previous text and is completed with recent results exposed in a seventh chapter. This is not a textbook, but the authors provide a good panorama of the state of the art. Starting from scratch, the first chapter is a sampler of the whole book. From then on, each chapter develops a particular aspect of graph homomorphisms and ends with historical remarks and a large list of exercises. The book is exceptionally rich, dense and well written. It also has the unique advantage, among many titles devoted to graph theory, of focusing on homomorphisms, frequently overlooked in favour of isomorphisms. Although the authors are very didactic, always discussing the relevance and motivation for developing new concepts, their mathematical concision turns the reading, essentially of proofs, into a real challenge to non-specialists. Mathematical crystallographers will certainly find some threads to follow. But I would like to invite the general crystallographer to make an effort which will most probably be rewarded. Indeed, graph homomorphisms provide a natural language to express many structural properties of crystalline materials, both ordered and disordered. As groups and group homomorphisms belong today to the necessary tool bag of any crystallographer, I am convinced that graphs and graph homomorphisms will become essential as well.

Before commenting on the text of the book, I feel compelled to dive into their subject, accompanying the reader through the exotic garden of homomorphisms. For this I chose a simple example: the framework SOD of sodalite. In this illustration I will follow freely the line developed in ch. 1 of the book, gently presenting graph-theoretical concepts in a concrete case. First then, the definition: a homomorphism h from a graph G to a graph H is a double-mapping from the vertex set of G to the vertex set of H, and from the edge set of G to the edge set of H subject to the condition that h(uv) = h(u)h(v), where uv designates the edge linking vertex u and vertex v. In simple words: h preserves adjacency.

Fig. 1 shows two homomorphisms, f from the building unit sod to the framework SOD and g from the framework SOD to its quotient graph, i.e. the graph of vertex- and edge-lattices of the framework, in this case the graph of the octahedron, noted as the complete tripartite graph .

Figure 1 Two homomorphisms: f from sod to SOD and g from SOD to .

The first one is injective and expresses the fact that sod is a building unit of SOD. The second one is surjective and regular; it can be associated to a description of the unit cell of the framework. One of the fundamental properties of homomorphisms is that they can be composed. Hence, we know that the mapping gf is a homomorphism from sod to . Given two graphs G and H, any homomorphism from G to H can be interpreted as a H-colouring of G. Thus the composition gf can be understood as a -colouring of sod, meaning that we may label vertices of sod by vertices of in such a way that the labels in sod respect the adjacency relations in . This is a powerful tool; for instance, we will check that gf is surjective. As a consequence, we deduce that SOD, described by these two homomorphisms, admits a unique building unit and we will be able to derive the whole framework. Better: we show that SOD is the only symmetrical framework satisfying these conditions. To this end, however, we need first to produce a -colouring of sod. But before pursuing the analysis, we go back to the text of the book.

Given two graphs G and H, one may ask about the existence of a homomorphism (noted G  H), the number of such homomorphisms and eventually the design of algorithms providing a particular homomorphism; each question requires a different set of methods. Ch. 1 quickly introduces the elementary concepts of graph theory and jumps to the main properties of homomorphisms and some general methodology. As illustration, the concepts are applied to small graphs, essentially paths, cycles, tournaments and complete graphs. The authors develop several adapted tools in later chapters. Ch. 1 also introduces the concept of a representation of a monoid, proving that every monoid is isomorphic to the endomorphism monoid of a suitable digraph. Ch. 4 deepens the result, showing that any finite category is isomorphic to the homomorphism category of some set of graphs.

Ch. 2 describes various constructions such as products, exponentiation, retractions and polymorphisms. A retraction is a homomorphism r from a graph G to a subgraph H such that r is the identity on H: one says that G retracts to H. A core is a graph that does not retract to a proper subgraph. For example, retracts to , the graph of the triangle, in this case any face of the octahedron; it is easily seen that is a core. This suggests the following algorithm to obtain a 3-colouring of : start with some face and label its vertices as 0, 1 and 2. For any face with already two vertices labelled as i and j, label the third vertex as (3-i-j). It appears that the algorithm succeeds in the sense that no adjacent vertices have received the same colour. We then observe that 6-cycles of sod should map to 6-cycles of ; indeed, the geometrical definition of sod implies that no two vertices in the cycle can be translationally equivalent. It follows that the composed homomorphism rgf from sod to wraps any 6-cycle twice around in the same direction or once in some direction and back the other way (the image of a cycle by a homomorphism is a closed walk). Counting these homomorphisms, we find, respectively, four of the former and 12 of the latter; in other words, they give rise, respectively, to four and 12 6-cycles. Now if we look for the highest symmetrical framework where all 6-cycles are equivalent, we must discard the latter since there are only 8 6-cycles in sod. We begin then with a 3-colouring of sod according to the following algorithm. Start with some 6-cycle of sod and label its vertices sequentially 0, 1, 2, 0, 1, 2. For any 6-cycle with an edge already labelled by i and j, label the two neighbours along this cycle as 3-i-j. It can be checked that the algorithm succeeds in the sense that it provides a 3-colouring of sod. Fig. 2 shows the -colouring of sod obtained after alternating black and red colours for every pair of vertices labelled with the same number 0, 1 or 2 within every 4- and 6-cycle of sod. (No two vertices in the same cycle can be translationally equivalent.) Here ends this digression, with the hope it can be of some help.

Figure 2 -colouring of sod; vertices with the same label (number and colour) belong to the same vertex-lattice in the framework, which is seen to be body-centred.

The binary relation (also noted ) is reflexive and transitive but it is not antisymmetric on the whole set of digraphs. However, because every digraph is homomorphically equivalent to a single core, the relation defines a partial order on the sets C_s and C of graphs and digraphs that are a core. Ch. 3 is devoted to the respective study, describing important results. For example, it is shown that C is a lattice and that C_s is dense with the only exception that there is no graph X with < X < . The pair [, ] is called a gap and is thus the only gap in C_s; in contrast, C admits many gaps: for each oriented tree T there is a digraph G such that [G, T] is a gap. However, if G < H, where H is a connected core and contains an oriented cycle, then [G, H] is not a gap. Gaps are in one-to-one correspondence with duality pairs: a pair of digraphs (F, H) from a suborder C′ C forms a simple duality pair in C′ if, for any G in C′, we have: F G if and only if G H. This is a most important property correlating the existence of some homomorphism to the nonexistence of another one.

The existence of homomorphisms is analysed from the algorithmic point of view in ch. 5. The H-COL problem asks whether there exists a homomorphism from a graph G to a given graph H. An important result to this end is the dichotomy theorem, which says that if a graph H contains a loop or is bipartite there exists a polynomial-time algorithm, otherwise H-COL is NP-complete. The authors list several algorithms, polynomial-time or NP-complete, which might fail or succeed depending on the input graph G. Failure of the algorithm generally indicates the nonexistence of a homomorphism. In case of success of the algorithm, additional duality properties of H may ensure H-colourability. But then no general technique is known to produce a homomorphism. In this context, many proofs use the replacement technique described in ch. 4, where arcs of a digraph are substituted by a suitable graph.

Chs. 6 and 7 propose various applications of the concepts and techniques exposed in the first chapters. For example, the well known chromatic numbers allow a classification of graphs through homomorphism to the class of complete graphs with < < . Circular and fractional chromatic (rational) numbers provide a finer classification through homomorphism to rational complete graphs and Kneser graphs K(n,k), respectively. Frequency assignment to transmitters is a practical problem that can be discussed in terms of homomorphisms. Another well known problem is related to counting homomorphisms. Indeed, a configuration which can be the assignment of spins, states or chemical species to the sites of a crystal structure, subject to some constraints, corresponds to a homomorphism from the given structure to some suitable graph. Counting configurations is then counting homomorphisms.

With these possible applications we are back to crystallography, even if the authors do not even come close. I mean that graph homomorphisms have huge potential to help tackle problems concerning crystal structure and phase transitions. The courageous reader will certainly grasp enough of homomorphisms from the book to apply to their own research interests.