Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications)
Pavol Hell, Jaroslav Nešet?il
Format: PDF / Kindle (mobi) / ePub
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.
having χ(G×H) ≤ 10, say. (In fact, this leads some to conclude the conjecture may well be false.) Somewhat surprisingly, it turns out that if one can ensure that χ(G × H) reaches ten by requiring G, H to have a high chromatic number, then the same will hold for any constant c in place of ten. 56 PRODUCTS AND RETRACTS Theorem 2.39 As k → ∞, the minimum chromatic number of the product of two graphs with chromatic number k, either tends to ∞, or is always smaller than ten. Let u(k) be the
and contains all the arcs (edges) of H HOMOMORPHISMS PRESERVE ADJACENCY 3 amongst the vertices in G. A clique in a graph G is a complete subgraph of G. All other standard notions (bipartite graph, planar graph, regular graph, etc.), will be used in their usual sense, as in, say, [36, 339]. These deﬁnitions mean that all our graphs and digraphs, and the more general systems to be introduced later, are ﬁnite. Occasionally, we will allow inﬁnite graphs or digraphs, in which case we make a point
. (The diﬀerence between the degree of i and n/2 is one half of the sum of Xij , since edges contribute 1 and nonedges −1.) We now claim that the probability that all degrees are between n2 (1 − ) and n2 (1 + ) tends to 1 as n → ∞. Indeed, the probability that there exists a vertex i with degree greater than n2 (1 + ) or smaller than n2 (1 − ) is at most n times the probability that a 2 particular vertex i has such a degree, which we have bounded by e− n/2 . Since 2 ne− n/2 tends to 0 as n tends
H. Therefore, H ∗ -colouring is N P -complete, and by Lemma 5.5 so is H-colouring, contrary to assumption 1. Next we show that H cannot contain a K4 . Otherwise, let J be an edge with end vertices j and k1 , and perform the sub-indicator construction on H with x1 being a vertex in a K4 . The resulting graph H + is nonbipartite, since it contains a triangle amongst the neighbours of x1 . On the other hand, H + does not contain x1 , hence it is a smaller graph than H. Once more, if H + -colouring
of I, and two of the three intervals have right endpoint not to the left of the right endpoint of I. Note that t is one of the three vertices x, y, z, and we deﬁne µ(x, y, z) = t. It is clear that if at least two of x, y, z are the same, say equal to a, then t = a. It remains to show that if xx , yy , zz ∈ E(H), then tt ∈ E(H) for t = µ(x, y, z) and t = µ(x , y , z ). Suppose to the contrary that It is disjoint from It , say It precedes It . Then at least two of Ix , Iy , Iz precede at least two