minimum number of groups required

Question

Can anyone please help me with the best approach for the below-mentioned problem?

Let's say there are n children. These children need to be divided into groups. But, the issue is there are some pairs m of children who don't want to go in same group. Can you tell the minimum number of groups we have to form?

Input Description:

First line will contain two non-negative integers n and m. Then next m lines will contain two non-negative integers which are the given pairs of children.

Input:
6 3
1 4
2 3
1 5

Output
2.

Explanation:
(1,2,6), (3,4,5) can be two groups which satisfy all the given conditions.

I see that this can be solved by converting it into a graph with edges between given pair of numbers and finding the chromatic number of it. Looking for better solutions than this.

Answer 1

This is the optimization variant of Vertex Coloring.

This problem is a known NP Complete problem (except for 2 coloring), so there is no known efficient solution to this problem for large graphs. For small graphs, you could try backtracking and/or branch& bound solutions.