How to partition disagreeable people into compatible groups We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals.   Partition the people into the minimum number of groups such that no person is grouped with someone they don't like.  (If A doesn't like B then A cannot be in a group with B. Each person must belong to exactly one group.)

The incompatibilities between people are given explicitly as unordered pairs of people that cannot be in a group together.

Consider one possible scenario involving 10 people where incompatibility pairs are given as follows:

(1,2) (1,6) (1,7) (2,3) (2,6) (2,7) (2,8) (3,4) (3,7) (3,8) (3,9)
(4,5) (4,8) (4,9) (4,10) (5,9) (5,10) (6,7) (7,8) (8,9) (9,10)


In this scenario it is unacceptable to form a group consisting of persons [ 1, 4, 5 ] because of the incompatibility pair (4,5), which means that persons 4 &amp; 5 are incompatible and cannot be in the same group.

For the scenario given above, we can divide people up optimally into groups that all get along, using no fewer than 4 groups.  Here is one such way of arranging people into 4 groups. 

GROUP #1 : [ 1, 3, 5 ]
GROUP #2 : [ 2, 4 ]
GROUP #3 : [ 6, 8, 10 ]
GROUP #4 : [ 7, 9 ]


Note, that the groups do not have to have the same number of members, and it is acceptable to have a group consisting of only one individual if necessary.  But each person must assigned to a group.

Describe an algorithm, given an arbitrary incompatibility matrix among N people in the form of zero or more incompatibility pairs, to determine a compatible grouping that uses the fewest groups possible.



EDIT:  Here's what I have tried so far.

A greedy algorithm:

While there are persons not yet assigned to a group.
   Take the lowest numbered unassigned person and create a new group `g` consisting of just them.
   For each person `p` not yet added to a group:
       If they are not incompatible with anyone in the current group `g`:
          Add person `p` to group `g`


I have no confidence at all that this would produce the minimal number of groups though.
You are essentially asking this:
"Given a graph $G=(V,E)$ where each vertex in $V$ denotes a person and each edge $(u,v) \in E$ means that $u$ is incompatible with $v$, what is the minimum number of colors required to color the vertices of $V$ such that no edge in $E$ has both endpoints of the same color?"

In other words, given any graph $G$ (which can always be realized with a suitable set of incompatibilities), find the chromatic number $\chi(G)$ of $G$. 

This is a well-known NP-hard problem. In particular, it is already NP-hard to decide whether $\chi(G) \le 3$.
For the special case of $2$ colors, $\chi(G) \le 2$ can be decided in linear time (just check whether $G$ is bipartite, which also gives you the corresponding coloring if that is the case).

However, since you are just asking for an algorithm (no mention of a polynomial-time complexity or even efficiency) you might as well enumerate all existing colorings in $O(3^{|V|} + \dots + \chi(G)^{|V|}) = O(\chi(G)^{|V|})$ time.
This can be improved to $O(2.2461^{|V|} )$ time, see:
https://epubs.siam.org/doi/10.1137/070683933

Finally, there is simple linear-time greedy algorithm that uses at most $\Delta(G)+1$ colors, where $\Delta(G)$ is the maximum degree of $G$: Examine the vertices of $G$ one at a time, color a vertex with any color that is not already used by any of its neighbors.

This is the relevant Wikipedia page: https://en.wikipedia.org/wiki/Graph_coloring .

EDIT

Your algorithm is iteratively computing maximal independent sets of $G$. Similarly to the greedy algorithm, it will return a coloring with at most $\Delta(G)+1$ colors. 
To see this, suppose that there is a vertex $v$ of color (group) $\Delta(G)+2$. Then, since $v$ has not been added to any of the first $\Delta(G)+1$ groups, it must have at least one neighbor in each of those groups. This means that the degree of $v$ is at least $\Delta(G)+1$, a contradiction.

Here is a tight example for both algorithms (vertices are examined in increasing order of their label):