Formally, let G = (V, E) be a graph, and suppose vertex set V is partitioned into m subsets V1, …, Vm, called "colors".
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 V1, …, Vm are the departments.
[4] 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.
Intuitively, when the departments Vi are larger, and there is less conflict between faculty members, an ISR should be more likely to exist.
For every subset S of colors, Hall's condition implies that S has at least |S| neighbors in Y, and therefore there are at least |S| edges of H adjacent to distinct vertices of Y.
For every subset S of colors, the graph GS contains at least 3|S| vertices, and it is a union of cycles of length divisible by 3 and paths.
Therefore IS is special for S. By the previous theorem, G has an ISR.One family of conditions is based on the homological connectivity of the independence complex of subgraphs.
then the partition V1, …, Vm admits an ISR.As an example,[4] suppose G is a bipartite graph, and its parts are exactly V1 and V2.
In this case [m] = {1,2} so there are four options for J: Every properly coloured triangle-free graph of chromatic number x contains a rainbow-independent set of size at least x⁄2.
[11] Several authors have studied conditions for existence of large rainbow-independent sets in various classes of graphs.
[4] The input to 3DM is a tripartite hypergraph (X + Y + Z, F), where X, Y, Z are vertex-sets of size m, and F is a set of triplets, each of which contains a single vertex of each of X, Y, Z.