Q:

Minimum number of partitions of a set given list of numbers that can't appear in the same partition

I wish to calculate the minimum number of partitions of a set required given a list of pairs of numbers that cannot appear together in the same partition.
Example 1:
$$S = [1,2,3,4,5,6]\\[5pt]
\text{Exclusive pairs} = (1,2), (3,4), (5,6), (1,6), (4,6)$$
I can create two partitions such that $p_1 = (1, 4, 5)$ and $p_2 = (2, 3, 6)$
Example 2:
$$S = [1,2,3,4,5,6]\\[5pt]
\text{Exclusive pairs} = (1,2), (4,5), (5,6), (1,6), (4,6)$$
That requires more than two partitions.  It appears to be because there's a "loop" created: $(4, 5) \to (5, 6) \to (6, 4)$ and back to the start again.
It seems that the minimum number of partitions might be $\#\text{loops} + 1$, although I'm not certain.  In any event I don't know an efficient way to detect such loops.
Am I on the right track here, and can you advise any techniques/algorithms that might help me?
This is actually a real world problem.  The wife has been tasked with splitting a school year group into classes, but there are pupils they don't want together in the same classes.  I'd like to be able to prove how many classes they would need given their list of exceptions (or alternatively that they can't physically have N classes given their list of exceptions).

A:

This sounds like the sort of combinatoric problem that can be NP-hard in the general case, but is actually easy in the real world.  A loop with an odd number of members forces three classes, but a loop with an even number does not.  If you had $(1,2),(2,3),(3,4),(4,1)$ you could make $\{1,3\}, \{2,4\}$ The number of loops doesn't matter-say your excluded pairs were $(3k+1,3k+2),(3k+2,3k+3),(3k+3,3k+1)$.  You can have lots of these and have only three classes.  
You can imagine your group as the vertices of a graph, the excluded pairs as edges, and you have an example of the graph coloring problem where you are looking for the chromatic number of your graph.  It seems likely that your graph breaks into many disconnected components, as you probably have groups of students who have restrictions between themselves, but don't care about the rest of the students.  You can work on each component separately, and the one that requires the most classes will be your answer.  You also might have a few very unpopular students.  Group them into as few classes as possible, then put the rest where you can.  Unless you have lots of exclusions it will be pretty easy to get an optimal assignment and show that it is optimal by showing some subset of the students that requires that many classes.

