Update all nodes in a graph in a way that at any step all chosen nodes are disconnected There are N nodes in a graph and some of them are connected with edges. All nodes are of type T1. The goal is to update all nodes to type T2. At any step you can choose any set of nodes and change their type to type T2 with the only restrictions that no nodes in the chosen set can be connected with an edge (i.e. this sub-graph should not have edges). Find the minimum number of steps required to update all nodes to type T2.

A graph can have any topology, i.e. nodes can be connected in a random fashion without any pattern
Hint: Your question is tantamount to finding a partition of the vertices of the graph into as few independent sets as possible. This is the same as finding the chromatic number of the graph, which is NP-complete.