Let G be graph whose vertex set is partitioned into classes. When
does there exist a set S of vertices, consisting of one vertex from
each class, such that no two vertices of S are joined by an edge of
G? Such a set is called an independent transversal of G
with respect to the given vertex partition. It turns out that many
mathematical questions can be formulated by asking whether an
independent transversal exists in a particular graph with a particular
vertex partition.
We describe a number of different conditions that guarantee the
existence of an independent transversal in a given vertex-partitioned
graph. We also outline some applications of these results in various
different contexts.
