On Rainbow Independent Sets
doc. RNDr. Gabriel Semanišin, PhD.
Ústav informatiky, PF UPJŠ
Motivated by a medical problem, we introduce the concept of rainbow sets and rainbow independent sets in graphs. Let G = (V, E) be a graph and (V1 , V2 , . . . , Vk ) be a partition of its vertex set V . We colour all vertices of the same partition by the same colour and vertices of distinct partitions by distinct colours. We call a set S ⊆ V containing at most one vertex of each partition rainbow. If a rainbow set S is moreover independent in G then it is called rainbow independent. Similar problems were studied in [1, 2]. We introduce and interrelate four problems dealing with rainbow independent sets and rainbow sets in graphs, determine their complexities and observe bounds for their invariants.