This is a book about graph homomorphisms. Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. The subject gives a useful perspective in areas such as graph reconstruction, products, fractional and circular colorings, and has applications in complexity theory, artificial intelligence, telecommunication, and, most recently, statistical physics. Based on the authors' lecture notes for graduate courses, this book can be used as a textbook for a second course in graph theory at 4th year or master's level and has been used for courses at Simon Fraser University (Vancouver), Charles University (Prague), ETH (Zurich), and UFRJ (Rio de Janeiro). The exercises vary in difficulty. The first few are usually intended to give the reader an opportunity to practice the concepts introduced in the chapter; the later ones explore related concepts, or even introduce new ones. For the harder exercises hints and references are provided. The authors are well known for their research in this area and the book will be invaluable to graduate students and researchers alike.
Author(s): Pavol Hell, Jaroslav Ne%set%ril
Series: Oxford Lecture Series in Mathematics and Its Applications
Publisher: Oxford University Press, USA
Year: 2004
Language: English
Pages: 257
Cover......Page 1
Oxford Lecture Series in Mathematics and its Applications Series Editors......Page 2
OXFORD LECTURE SERIES IN MATHEMATICS AND ITS APPLICATIONS......Page 3
Title page......Page 4
Copyright page......Page 5
Preface......Page 6
CONTENTS......Page 12
1.1 Graphs, digraphs, and homomorphisms......Page 14
1.2 Homomorphisms preserve adjacency......Page 16
1.3 Homomorphisms generalize colourings......Page 19
1.4 The existence of homomorphisms......Page 23
1.5 Homomorphisms generalize isomorphisms......Page 29
1.6 Homomorphic equivalence......Page 31
1.7 The composition of homomorphisms......Page 33
1.8 Homomorphisms model assignments and schedules......Page 40
1.9 Remarks......Page 46
1.10 Exercises......Page 47
2.1 The product......Page 50
2.2 Dimension......Page 53
2.3 The Lovasz vector and the Reconstruction Conjecture......Page 56
2.4 Exponential digraphs......Page 59
2.5 Shift graphs......Page 60
2.6 The Product Conjecture and graph multiplicativity......Page 63
2.7 Projective digraphs and polymorphisms......Page 70
2.8 The retract......Page 71
2.9 Isometric trees and cycles......Page 73
2.10 Reflexive absolute retracts......Page 77
2.11 Reflexive dismantlable graphs......Page 81
2.12 Median graphs......Page 85
2.13 Remarks......Page 89
2.14 Exercises......Page 91
3.1 The partial orders $\mathcal{C}$ and $\mathcal{C}_S$......Page 94
3.2 Representing ordered sets......Page 95
3.3 Incomparable graphs and maximal antichains in $\mathcal{C}_S$......Page 98
3.4 Sparse graphs with specified homomorphisms......Page 102
3.5 Incomparable graphs with additional properties......Page 106
3.6 Incomparable graphs on n vertices......Page 107
3.7 Density......Page 109
3.8 Duality and gaps......Page 111
3.9 Maximal antichains in C......Page 114
3.10 Bounds......Page 115
3.11 Remarks......Page 119
3.12 Exercises......Page 120
4.2 Rigid digraphs......Page 122
4.3 An excursion to infinity......Page 128
4.4 The replacement operation......Page 130
4.5 Categories......Page 135
4.6 Representation......Page 141
4.7 A combinatorial obstacle to representation......Page 145
4.8 Some categories are not rich enough......Page 148
4.9 Remarks......Page 151
4.10 Exercises......Page 152
5.1 The $H$-colouring problem......Page 155
5.2 Dichotomy for graphs......Page 156
5.3 Digraph homomorphisms and CSPs......Page 164
5.4 Duality and consistency......Page 174
5.5 Pair consistency and majority functions......Page 179
5.6 List homomorphisms and retractions......Page 183
5.7 Trigraph homomorphisms......Page 191
5.8 Generalized split graphs......Page 196
5.9 Remarks......Page 199
5.10 Exercises......Page 200
6.1 Circular colourings......Page 205
6.2 Fractional colourings......Page 213
6.3 $T$-colourings......Page 223
6.4 Oriented and acyclic colourings......Page 225
6.5 Remarks......Page 231
6.6 Exercises......Page 232
References......Page 235
Index......Page 252
