Update all nodes in a graph in a way that at any step all chosen nodes are disconnected
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.