If the graph is not bipartite, it is not possible to group the nodes.

Notice that we can solve the problem for each connected component independently, and the final answer will be just the sum of the maximum number of groups in each component.

Finally, to solve the problem for each connected component, we can notice that if for some node v we fix its position to be in the leftmost group, then we can also evaluate the position of every other node. That position is the depth of the node in a bfs tree after rooting at node v.