Graphs and homomorphisms.

*(English)*Zbl 1062.05139
Oxford Lecture Series in Mathematics and its Applications 28. Oxford: Oxford University Press (ISBN 0-19-852817-5/hbk). xii, 244 p. (2004).

This is a textbook for a second course in graph theory, directed primarily at graduate students, presented in the context of homomorphisms between directed graphs, mostly but not always finite. Paraphrasing the chapter descriptions in the authors’ preface, we have the following.

Chapter 1 is a motivational “mini-sampler” of some of the material in later chapters. Chapter 2 focuses on certain basic constructions such as product and retract. A directed graph \(G\) is said to retract to a subgraph \(H\) if there exists a homomorphism \(r:G\to H\) such that the restriction of \(r\) to \(H\) is the identity on \(H\). Chapter 3 presents the order relation that homomorphisms induce on sets of directed graphs, in particular the partial order induced on the set of cores, a core being a directed graph that retracts to no proper subgraph. Chapter 4 “explores the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs.” Infinite rigid graphs (i.e., graphs whose only homomorphism into themselves is the identity) of arbitrary cardinality are constructed. In Chapter 5, the authors “explore algorithmic aspects of graph homomorphisms and of similar partition problems.” Inasmuch as a proper vertex-coloring of a graph \(G\) may be regarded as a homomorphism from \(G\) into a complete graph, Chapter 6 considers variations of coloring problems, such as circular colorings, in the context of graph homomorphisms. Each chapter concludes with a set of between 18 and 30 exercises.

Chapter 1 is a motivational “mini-sampler” of some of the material in later chapters. Chapter 2 focuses on certain basic constructions such as product and retract. A directed graph \(G\) is said to retract to a subgraph \(H\) if there exists a homomorphism \(r:G\to H\) such that the restriction of \(r\) to \(H\) is the identity on \(H\). Chapter 3 presents the order relation that homomorphisms induce on sets of directed graphs, in particular the partial order induced on the set of cores, a core being a directed graph that retracts to no proper subgraph. Chapter 4 “explores the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs.” Infinite rigid graphs (i.e., graphs whose only homomorphism into themselves is the identity) of arbitrary cardinality are constructed. In Chapter 5, the authors “explore algorithmic aspects of graph homomorphisms and of similar partition problems.” Inasmuch as a proper vertex-coloring of a graph \(G\) may be regarded as a homomorphism from \(G\) into a complete graph, Chapter 6 considers variations of coloring problems, such as circular colorings, in the context of graph homomorphisms. Each chapter concludes with a set of between 18 and 30 exercises.

Reviewer: Mark E. Watkins (Syracuse)

##### MSC:

05C99 | Graph theory |

05C15 | Coloring of graphs and hypergraphs |

05C20 | Directed graphs (digraphs), tournaments |

05C62 | Graph representations (geometric and intersection representations, etc.) |

06A07 | Combinatorics of partially ordered sets |