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 V1, …, Vm, 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 Vi. 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 V1, …, Vm are the departments.
Variants It is assumed for convenience that the sets V1, …, Vm 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 Vi contains x. In the resulting graph, connect all copies of x to each other. In the new graph, the Vi 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.
Existence of rainbow-independent sets There are various sufficient conditions for the existence of an ISR.
Condition based on vertex degree Intuitively, when the departments Vi 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. This is formalized by the following theorem: If the degree of every vertex in G is at most d, and the size of each color-set is at least 2d, then G has an ISR. The 2d is best possible: there are graph with vertex degree k and colors of size 2d – 1 without an ISR. But there is a more precise version in which the bound depends both on d and on m.
Condition based on dominating sets Below, given a subset S of colors (a subset of {V1, ..., Vm} ), we denote by US the union of all subsets in S (all vertices whose color is one of the colors in S), and by GS the subgraph of G induced by US. The following theorem describes the structure of graphs that have no ISR but are edge-minimal, in the sense that whenever any edge is removed from them, the remaining graph has an ISR. If G has no ISR, but for every edge e in E, G-e has an ISR, then for every edge e = (x, y) in E, there exists a subset S of the colors {V1, …, Vm}, and a set Z of edges of GS, such that: The vertices x and y are both in US; The edge e = (x, y) is in Z; The set of vertices adjacent to Z dominates GS; |Z| ≤ |S| − 1; Z is a matching – no two edges of it are adjacent to the same vertex.
Hall-type condition Below, given a subset S of colors (a subset of {V1, …, Vm} ), an independent set IS of GS is called special for S if for every independent subset J of vertices of GS of size at most |S| − 1, there exists some v in IS such that J ∪ {v} is also independent. Figuratively, IS is a team of "neutral members" for the set S of departments, that can augment any sufficiently small set of non-conflicting members, to create a larger such set. The following theorem is analogous to Hall's marriage theorem:If, for every subset S of colors, the graph GS contains an independent set IS that is special for S, then G has an ISR.Proof idea. The theorem is proved using Sperner's lemma. The standard simplex with m endpoints is assigned a triangulation with some special properties. Each endpoint i of the simplex is associated with the color-set Vi, each face {i1, …, ik} of the simplex is associated with a set S = {Vi1, …, Vik} of colors. Each point x of the triangulation is labeled with a vertex g(x) of G such that: (a) For each point x on a face S, g(x) is an element of IS – the special independent set of S. (b) If points x and y are adjacent in the 1-skeleton of the triangulation, then g(x) and g(y) are not adjacent in G. By Sperner's lemma, there exists a sub-simplex in which, for each point x, g(x) belongs to a different color-set; the set of these g(x) is an ISR. The above theorem implies Hall's marriage condition. To see this, it is useful to state the theorem for the special case in which G is the line graph of some other graph H; this means that every vertex of G is an edge of H, and every independent set of G is a matching in H. The vertex-coloring of G corresponds to an edge-coloring of H, and a rainbow-independent-set in G corresponds to a rainbow-matching in H. A matching IS in HS is special for S, if for every matching J in HS of size at most |S| − 1, there is an edge e in IS such that J ∪ {e} is still a matching in HS. Let H be a graph with an edge-coloring. If, for every subset S of colors, the graph HS contains a matching MS that is special for S, then H has a rainbow-matching. Let H = (X + Y, E) be a bipartite graph satisfying Hall's condition. For each vertex i of X, assign a unique color Vi to all edges of H adjacent to i. 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. Let IS be a set of |S| such edges. For any matching J of size at most |S| − 1 in H, some element e of IS has a different endpoint in Y than all elements of J, and thus J ∪ {e} is also a matching, so IS is special for S. The above theorem implies that H has a rainbow matching MR. By definition of the colors, MR is a perfect matching in H.
… excerpt ends here. Continue reading the full article.
