Graphs and Homomorphisms

<jats:title>Abstract</jats:title> <jats:p>This is a book about graph homomorphisms, intended to introduce this exciting topic to a wide audience. It attempts to bring together what the authors see as the highlights of the theory and its many applications, and could be read as a sampler of this rich theory, and its most interesting results, techniques, and applications, with the hope that the reader will be motivated to further explore the rich literature. It tries not to set its focus too narrowly, bringing together the disparate sources of results, techniques, and points of view; these vary, from algebraic, to algorithmic, applied, extremal, and randomized. This is a second edition of a 2004 OUP book that appeared in the Oxford Lecture Series in Mathematics and Its Applications; the second edition was necessitated by the explosive development that the field underwent in the past two decades. As in the first edition, the topics cover the connections with classical combinatorial notions like graph colourings and products, with algebraic concepts like monoids and categories, and with algorithmic issues related to deciding the existence of a homomorphism. It is updated with the recent breakthroughs in several areas, and discusses, for example, the disproof of Hedetniemi’s product conjecture and the proof of the Feder–Vardi dichotomy conjecture. Moreover, many new topics are introduced, related to sparsity, logic, model theory, and the convergence of structures.</jats:p>