Graphs and Homomorphisms
Discrete mathematics is flourishing in the last decades, hand in hand with the development of computer science, and graph theory has now become a well established discipline within discrete mathematics. Algebra, on the other hand, belongs to classical disciplines. The two disciplines meet in this excellent book where graphs are studied by algebraic and categorical methods. The book is written by world known experts on structural and computational aspects of graph homomorphisms. As the first monograph systematically devoted to the subject, it will undoubtedly become a cornerstone of this theory. Graph homomorphisms generalize the notion of graph colouring in a natural way, and the book starts with graph colourings as first examples in the introductory chapter to be concluded with a review of special variants of this notion (fractional, circular and acyclic colourings) in the last chapter. On the path leading to this conclusion, the reader is led through such areas as classical categorical approach of products and retracts in Chapter 2, notions of duality, gaps and density in the homomorphism partial order of graphs in Chapter 3, the concept of rigidness and endomorphisms in Chapter 4 and computational aspects of graph homomorphisms, also related to the Constrained Satisfaction Problem, in Chapter 5. The exposition is self-contained, complemented with numerous exercises and remarks. Stemming from own experience of the authors at several renown world universities, this is an excellent textbook for graduate courses, but can serve equally well as a prime source of references and a source of open problems to researchers actively working in the area.