Is the problem "MIN-SET-PARTITION" an NP-hard problem?

Question

Given a family of sets $F = S_1, ..., S_n$ of elements from a universe $U$, find the minimal integer $k$ for which there is a partition of $F$ of size $k$, such that every two sets in the same partition are disjoint. Formally, we want $P_1, ..., P_k$ such that for every $1 \leq i,j \leq k$, we have $P_i \subseteq F$ and $P_i \cap P_j = \emptyset$. Furthermore, for every $S,T \in P_i$ we have $S \cap T = \emptyset$. Finally, $\bigcup P_i = F$.

We can ask the same question as a decision problem: $\lbrace U,F,k \rbrace \in MIN-SET-PARTITION$ iff there is a partition (as described above) of $F$ of size $k$.

My intuition is that this is indeed NP-hard and that someone has probably already thought about it. I'd be happy to get a reference or a description of a reduction.

Thanks!

Answer 1

Take $S_i$ to be the edges of a graph $G$. Then, a partition $F$ of size $k$ corresponds to an edge-coloring of $G$; the minimum such $k$ corresponds to the chromatic index of $G$. Edge-coloring is known to be NP-complete: "The NP-Completeness of Edge-Colouring".