# Prednáška

# On Rainbow Independent Sets

## doc. RNDr. Gabriel Semanišin, PhD.

Ústav informatiky, PF UPJŠ

22. februára 2017 (streda) o 12:45

SJ2S07 (3.16T), PF UPJŠ

## Abstrakt

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 (V_{1} , V_{2} , . . . , V_{k} ) 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.