Rainbow-independent set

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color. Formally, let G = (V, E) be a graph, and suppose vertex set V is partitioned into m subsets V_1, ..., V_m, called "colors". A set U of vertices is called a rainbow-independent set if it satisfies both the following conditions: It is an independent set – every two vertices in U are not adjacent (there is no edge between them); It is a rainbow set – U contains at most a single vertex from each color V_i. Other terms used in the literature are independent set of representatives, independent transversal, and independent system of representatives. As an example application, consider a faculty with m departments, where some faculty members dislike each other. The dean wants to construct a committee with m members, one member per department, but without any pair of members who dislike each other. This problem can be presented as finding an ISR in a graph in which the nodes are the faculty members, the edges describe the "dislike" relations, and the subsets V_1, ..., V_m are the departments. It is assumed for convenience that the sets V_1, ..., V_m are pairwise-disjoint. In general the sets may intersect, but this case can be easily reduced to the case of disjoint sets: for every vertex x, form a copy of x for each i such that V_i contains x. In the resulting graph, connect all copies of x to each other. In the new graph, the V_i are disjoint, and each ISR corresponds to an ISR in the original graph. ISR generalizes the concept of a system of distinct representatives (SDR, also known as transversal). Every transversal is an ISR where in the underlying graph, all and only copies of the same vertex from different sets are connected. There are various sufficient conditions for the existence of an ISR. Intuitively, when the departments V_i are larger, and there is less conflict between faculty members, an ISR should be more likely to exist. The "less conflict" condition is represented by the vertex degree of the graph.