The theory of directed graphs has developed enormously over recent decades, yet this book
(first published in 2000) remains the only book to cover more than a small fraction of the …

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 …

Let H be a fixed graph, whose vertices are referred to as 'colors'. An H-coloring of a graph G
is an assignment of 'colors' to the vertices of G such that adjacent vertices of G obtain …

The problem of counting homomorphisms from a general graph G to a fixed graph H is a
natural generalization of graph coloring, with important applications in statistical physics …

Abstract The Three Color Problem is: Under what conditions can the regions of a planar map
be colored in three colors so that no two regions with a common boundary have the same …

This is the fifth edition of a quarterly column the purpose of which is to provide continuing
coverage of new developments in the theory of NP-completeness. The presentation is …

This paper is the first part of an introduction to the subject of graph homomorphism in the
mixed form of a course and a survey. We give the basic definitions, examples and uses of …

This paper examines the effect of a graph homomorphism upon the chromatic difference
sequence of a graph. Our principal result (Theorem 2) provides necessary conditions for the …

For directed graphs G and H, we say that G is H-colorable, if there is a graph homomorphism
from G into H; that is, there is a mapping f from the vertex set of G into the vertex set of H …

The following problem, known as the H-colouring problem, is studied. An H-colouring of a
directed graph D is a mapping f:V(D)→V(H) such that (f(x),f(y)) is an edge of H whenever …