I have the following question: Given graph $ G=(V,E)$ with given order on its vertices, I mean $ v_1<v_2<…<v_n$ I need to find minimal colors ordered paining of the graph vertices s.t neighbor vertices don’t have the same color, I mean: $ (v_1,v_2,…,v_j)$ – painted in fist color and non of them are neighbors. $ (v_{j+1},…,v_l)$ – painted in second color and non of them are neighbors. and so on.

The complexity needs to be $ O(V+E)$ . Anyone have an idea?