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 …

Constraint satisfaction problems have enjoyed much attention since the early seventies, and
in the last decade have become also a focus of attention amongst theoreticians. Graph …

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for
most classes of structured graphs. In contrast, we show that packing a maximum number of …

We consider the problem of partitioning the node set of a graph into p cliques and k stable
sets, namely the (p, k)-coloring problem. Results have been obtained for general graphs …

It is well known that a clique with k+ 1 vertices is the only minimal obstruction to k-
colourability of chordal graphs. A similar result is known for the existence of a cover by ℓ …

We discuss partition problems that generalize graph colouring and homomorphism
problems, and occur frequently in the study of perfect graphs. Depending on the pattern, we …

Ordinary colourings of cographs are well understood; we focus on more general colourings,
known as matrix partitions. We show that all matrix partition problems for cographs admit …

Given a symmetric m by m matrix M over 0, 1,*, the M-partition problem asks whether or not
an input graph G can be partitioned into m parts corresponding to the rows (and columns) of …

We show that one can compute the injective chromatic number of a chordal graph G at least
as efficiently as one can compute the chromatic number of (G− B) 2, where B are the bridges …

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They
are defined by the existence of a certain partition of vertices, which is NP-complete to decide …