Finding Independent Transversals Efficiently

Alessandra Graf, Penny Haxell

We give an efficient algorithm that, given a graph $G$ and a partition $V_1,\dots ,V_m$ of its vertex set, finds either an independent transversal (an independent set $\{v_1,\ldots…