Finding independent transversals efficiently

We give an efficient algorithm that, given a graph G and a partition V-1,..., V-m of its vertex set, finds either an independent transversal (an independent set {nu(1),..., nu(m)} in G such that nu 1 is an element of V-1 for each i), or a subset B of vertex classes such that the subgraph of G induced by boolean OR B has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been used to solve many other problems. Thus we are able to give algorithmic versions of many of these applications, a few of which we describe explicitly here.