Rainbow-independent set

Last updated November 03, 2024

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

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, \dots, V m$ are the departments.^[3]

Variants

It is assumed for convenience that the sets $V 1, \dots, 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.^[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.

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 $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. This is formalized by the following theorem:^[5]^: Thm.2

If the degree of every vertex in $G$ is at most $d$ , and the size of each color-set is at least $2 d$ , then $G$ has an ISR.

The $2 d$ is best possible: there are graph with vertex degree $k$ and colors of size $2 d - 1$ without an ISR.^[6] But there is a more precise version in which the bound depends both on $d$ and on $m$ .^[7]

Condition based on dominating sets

Below, given a subset $S$ of colors (a subset of ${V 1, ..., V m}$ ), we denote by $U S$ the union of all subsets in $S$ (all vertices whose color is one of the colors in $S$ ), and by $G S$ the subgraph of $G$ induced by $U S$ .^[8] 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 ${V 1, \dots, V m},$ and a set $Z$ of edges of $G S$ , such that:
The vertices $x$ and $y$ are both in $U S$ ;
The edge $e = (x, y)$ is in $Z$ ;
The set of vertices adjacent to $Z$ dominates $G S$ ;
$| Z | \leq | 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 ${V 1, \dots, V m}$ ), an independent set $I S$ of $G S$ is called special for $S$ if for every independent subset $J$ of vertices of $G S$ of size at most $| S | - 1$ , there exists some $v$ in $I S$ such that $J \cup {v}$ is also independent. Figuratively, $I S$ 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:^[9]

If, for every subset S of colors, the graph $G S$ contains an independent set $I S$ that is special for $S$ , then $G$ has an ISR.

Proof idea. The theorem is proved using Sperner's lemma.^[3]^: Thm.4.2 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 $V i$ , each face ${i 1, \dots, i k}$ of the simplex is associated with a set $S = {V i 1, \dots, V ik}$ 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 $I S$ – 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 $I S$ in $H S$ is special for $S$ , if for every matching $J$ in $H S$ of size at most $| S | - 1$ , there is an edge $e$ in $I S$ such that $J \cup {e}$ is still a matching in $H S$ .

Let $H$ be a graph with an edge-coloring. If, for every subset $S$ of colors, the graph $H S$ contains a matching $M S$ 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 $V i$ 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 $I S$ be a set of $| S |$ such edges. For any matching $J$ of size at most $| S | - 1$ in $H$ , some element $e$ of $I S$ has a different endpoint in $Y$ than all elements of $J$ , and thus $J \cup {e}$ is also a matching, so $I S$ is special for $S$ . The above theorem implies that $H$ has a rainbow matching $M R$ . By definition of the colors, $M R$ is a perfect matching in $H$ .

Another corollary of the above theorem is the following condition, which involves both vertex degree and cycle length:^[3]^: Thm.4.3

If the degree of every vertex in $G$ is at most 2, and the length of each cycle of $G$ is divisible by 3, and the size of each color-set is at least 3, then $G$ has an ISR.

Proof. For every subset $S$ of colors, the graph $G S$ contains at least $3 | S |$ vertices, and it is a union of cycles of length divisible by 3 and paths. Let $I S$ be an independent set in $G S$ containing every third vertex in each cycle and each path. So $| I S |$ contains at least $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}3|S|⁄3 = |S|$ vertices. Let $J$ be an independent set in $G S$ of size at most $| S | - 1$ . Since the distance between each two vertices of $I S$ is at least 3, every vertex of $J$ is adjacent to at most one vertex of $I S$ . Therefore, there is at least one vertex of $I S$ which is not adjacent to any vertex of $J$ . Therefore $I S$ is special for $S$ . By the previous theorem, $G$ has an ISR.

Condition based on homological connectivity

One family of conditions is based on the homological connectivity of the independence complex of subgraphs. To state the conditions, the following notation is used:

$Ind(G)$ denotes the independence complex of a graph $G$ (that is, the abstract simplicial complex whose faces are the independent sets in $G$ ).
$η H (X)$ denotes the homological connectivity of a simplicial complex $X$ (i.e., the largest integer $k$ such that the first $k$ homology groups of $X$ are trivial), plus 2.
$[m]$ is the set of indices of colors, ${1, \dots, n}.$ For any subset $J$ of $[m]$ , $V J$ is the union of colors $V J$ for $J$ in $J$ .
$G [V J]$ is the subgraph of $G$ induced by the vertices in $V J$ .

The following condition is implicit in ^[9] and proved explicitly in.^[10]

If, for all subsets $J$ of $[m]$ :
$\eta _{H}({\text{Ind}}(G[V_{J}]))\geq |J|$
then the partition $V 1, \dots, V m$ admits an ISR.

As an example,^[4] suppose $G$ is a bipartite graph, and its parts are exactly $V 1$ and $V 2$ . In this case $[m] = {1,2}$ so there are four options for $J$ :

$J = {}:$ then $G [J] = {}$ and $Ind(G [J]) = {}$ and the connectivity is infinite, so the condition holds trivially.
$J = {1}:$ then $G [J]$ is a graph with vertices $V 1$ and no edges. Here all vertex sets are independent, so $Ind(G [J])$ is the power set of $V 1$ , i.e., it has a single $n$ -simplex (and all its subsets). It is known that a single simplex is $k$ -connected for all integers $k$ , since all its reduced homology groups are trivial (see simplicial homology). Hence the condition holds.
$J = {2}:$ this case is analogous to the previous one.
$J = {1,2}:$ then $G [J] = G$ , and $Ind(G)$ contains two simplices $V 1$ and $V 2$ (and all their subsets). The condition $η H (Ind(G)) \geq 2$ is equivalent to the condition that the homological connectivity of $Ind(G)$ is at least 0, which is equivalent to the condition that ${\tilde {H_{0}}}({\text{Ind}}(G))$ is the trivial group. This holds if-and-only-if the complex $Ind(G)$ contains a connection between its two simplices $V 1$ and $V 2$ . Such a connection is equivalent to an independent set in which one vertex is from $V 1$ and one is from $V 2$ . Thus, in this case, the condition of the theorem is not only sufficient but also necessary.

Other conditions

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.^[1]^[12]

Computation

The ISR decision problem is the problem of deciding whether a given graph $G = (V, E)$ and a given partition of $V$ into $m$ colors admits a rainbow-independent set. This problem is NP-complete. The proof is by reduction from the 3-dimensional matching problem (3DM).^[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$ . An input to 3DM can be converted into an input to ISR as follows:

For each edge $(x, y, z)$ in $F$ , there is a vertex $v x,y,z$ in $V$ ;
For each vertex $z$ in $Z$ , let $V z = {v x,y,z | x \in X, y \in Y}.$
For each $x$ , $y 1$ , $y 2$ , $z 1$ , $z 2$ , there is an edge $(v x, y 1, z 1, v x, y 2, z 2)$ in $E$ ;
For each $x 1$ , $x 2$ , $y$ , $z 1$ , $z 2$ , there is an edge $(v x 1, y, z 1, v x 2, y, z 2)$ in $E$ ;

In the resulting graph $G = (V, E)$ , an ISR corresponds to a set of triplets $(x, y, z)$ such that:

Each triplet has a different $z$ value (since each triplet belongs to a different color-set $V z$ );
Each triplet has a different $x$ value and a different $y$ value (since the vertices are independent).

Therefore, the resulting graph admits an ISR if and only if the original hypergraph admits a 3DM.

An alternative proof is by reduction from SAT.^[3]

Related concepts

If $G$ is the line graph of some other graph $H$ , then the independent sets in $G$ are the matchings in $H$ . Hence, a rainbow-independent set in $G$ is a rainbow matching in $H$ . See also matching in hypergraphs.

Another related concept is a rainbow cycle, which is a cycle in which each vertex has a different color.^[13]

When an ISR exists, a natural question is whether there exist other ISRs, such that the entire set of vertices is partitioned into disjoint ISRs (assuming the number of vertices in each color is the same). Such a partition is called strong coloring .

Using the faculty metaphor:^[3]

A system of distinct representatives is a committee of distinct members, with or without conflicts.
An independent set is a committee with no conflict.
An independent transversal is a committee with no conflict, with exactly one member from each department.
A graph coloring is a partitioning of the faculty members into committees with no conflict.
A strong coloring is a partitioning of the faculty members into committees with no conflict and with exactly one member from each department. Thus this problem is sometimes called the happy dean problem.

A rainbow clique or a colorful clique is a clique in which every vertex has a different color.^[10] Every clique in a graph corresponds to an independent set in its complement graph. Therefore, every rainbow clique in a graph corresponds to a rainbow-independent set in its complement graph.

Related Research Articles

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let $r$ and $s$ be any two positive integers. Ramsey's theorem states that there exists a least positive integer $R (r, s)$ for which every blue-red edge colouring of the complete graph on $R (r, s)$ vertices contains a blue clique on $r$ vertices or a red clique on $s$ vertices. (Here $R (r, s)$ signifies an integer that depends on both $r$ and $s$ .)

In mathematics, Hall's marriage theorem, proved by Philip Hall, is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements. This number is called the width of the partial order. The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.

<span class="mw-page-title-main">3-dimensional matching</span>

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.$

In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

In graph theory, perfect matching in high-degree hypergraphs is a research avenue trying to find sufficient conditions for existence of a perfect matching in a hypergraph, based only on the degree of vertices or subsets of them.

In graph theory, there are two related properties of a hypergraph that are called its "width". Given a hypergraph H = (V, E), we say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K. Then:

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index k such that all reduced homological groups up to and including k are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.

The blow-up lemma, proved by János Komlós, Gábor N. Sárközy, and Endre Szemerédi in 1997, is an important result in extremal graph theory, particularly within the context of the regularity method. It states that the regular pairs in the statement of Szemerédi's regularity lemma behave like complete bipartite graphs in the context of embedding spanning graphs of bounded degree.

References

1 2 Aharoni, Ron; Briggs, Joseph; Kim, Jinha; Kim, Minki (2019-09-28). "Rainbow independent sets in certain classes of graphs". arXiv: 1909.13143 [math.CO].
↑ Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-10-01). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 1865-8784. S2CID 119139740.
1 2 3 4 5 6 Haxell, P. (2011-11-01). "On Forming Committees". The American Mathematical Monthly. 118 (9): 777–788. doi:10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
1 2 3 4 Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.
↑ E, HaxellP (2001-07-01). "A Note on Vertex List Colouring". Combinatorics, Probability and Computing. 10 (4): 345–347. doi:10.1017/s0963548301004758. S2CID 123033316.
↑ Szabó*, Tibor; Tardos†, Gábor (2006-06-01). "Extremal Problems For Transversals In Graphs With Bounded Degree". Combinatorica. 26 (3): 333–351. doi:10.1007/s00493-006-0019-9. hdl: 20.500.11850/24692 . ISSN 1439-6912. S2CID 15413015.
↑ Haxell, Penny; Szabó, Tibor (2006-01-01). "Odd Independent Transversals are Odd". Combinatorics, Probability and Computing. 15 (1–2): 193–211. doi:10.1017/S0963548305007157 (inactive 1 November 2024). ISSN 1469-2163. S2CID 6067931.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)
↑ Berke, Robert; Haxell, Penny; Szabó, Tibor (2012). "Bounded transversals in multipartite graphs". Journal of Graph Theory. 70 (3): 318–331. doi:10.1002/jgt.20618. ISSN 1097-0118. S2CID 17608344.
1 2 Aharoni, Ron; Haxell, Penny (2000). "Hall's theorem for hypergraphs". Journal of Graph Theory. 35 (2): 83–88. doi:10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.
1 2 Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.
↑ Aravind, N. R.; Cambie, Stijn; van Batenburg, Wouter Cames; de Verclos, Rémi de Joannis; Kang, Ross J.; Patel, Viresh (2020-03-15). "Structure and colour in triangle-free graphs". arXiv: 1912.13328 [math.CO].
↑ Kim, Jinha; Kim, Minki; Kwon, O.-joung (2020-02-05). "Rainbow independent sets on dense graph classes". arXiv: 2001.10566 [math.CO].
↑ Aharoni, Ron; Briggs, Joseph; Holzman, Ron; Jiang, Zilin (2021). "Rainbow Odd Cycles". SIAM Journal on Discrete Mathematics. 35 (4): 2293–2303. arXiv: 2007.09719 . doi:10.1137/20M1380557. S2CID 220647170.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 Aharoni, Ron; Briggs, Joseph; Kim, Jinha; Kim, Minki (2019-09-28). "Rainbow independent sets in certain classes of graphs". arXiv: 1909.13143 [math.CO].

[2] Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-10-01). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 1865-8784. S2CID 119139740.

[:2-3] 1 2 3 4 5 6 Haxell, P. (2011-11-01). "On Forming Committees". The American Mathematical Monthly. 118 (9): 777–788. doi:10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.

[:1-4] 1 2 3 4 Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.

[5] E, HaxellP (2001-07-01). "A Note on Vertex List Colouring". Combinatorics, Probability and Computing. 10 (4): 345–347. doi:10.1017/s0963548301004758. S2CID 123033316.

[6] Szabó*, Tibor; Tardos†, Gábor (2006-06-01). "Extremal Problems For Transversals In Graphs With Bounded Degree". Combinatorica. 26 (3): 333–351. doi:10.1007/s00493-006-0019-9. hdl: 20.500.11850/24692 . ISSN 1439-6912. S2CID 15413015.

[7] Haxell, Penny; Szabó, Tibor (2006-01-01). "Odd Independent Transversals are Odd". Combinatorics, Probability and Computing. 15 (1–2): 193–211. doi:10.1017/S0963548305007157 (inactive 1 November 2024). ISSN 1469-2163. S2CID 6067931.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)

[8] Berke, Robert; Haxell, Penny; Szabó, Tibor (2012). "Bounded transversals in multipartite graphs". Journal of Graph Theory. 70 (3): 318–331. doi:10.1002/jgt.20618. ISSN 1097-0118. S2CID 17608344.

[:4-9] 1 2 Aharoni, Ron; Haxell, Penny (2000). "Hall's theorem for hypergraphs". Journal of Graph Theory. 35 (2): 83–88. doi:10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.

[:3-10] 1 2 Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

[11] Aravind, N. R.; Cambie, Stijn; van Batenburg, Wouter Cames; de Verclos, Rémi de Joannis; Kang, Ross J.; Patel, Viresh (2020-03-15). "Structure and colour in triangle-free graphs". arXiv: 1912.13328 [math.CO].

[12] Kim, Jinha; Kim, Minki; Kwon, O.-joung (2020-02-05). "Rainbow independent sets on dense graph classes". arXiv: 2001.10566 [math.CO].

[13] Aharoni, Ron; Briggs, Joseph; Holzman, Ron; Jiang, Zilin (2021). "Rainbow Odd Cycles". SIAM Journal on Discrete Mathematics. 35 (4): 2293–2303. arXiv: 2007.09719 . doi:10.1137/20M1380557. S2CID 220647170.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]