Paint graph ordered vertices
If understand the question correctly you want to find a $k$-coloring of the given graph, given an ordered list of the vertex such that vertex with the same colors are consecutive in this list.

If that is the case then this problem can be solved greedy. 

We should only find maximal independent sets which are contiguous segments in your list starting from the beginning. Start with an empty set. Go for every vertex in the ordered list, if the vertex is not connected to any other node in the set, include it. Otherwise, paint all vertex in the set with the same color, notice they form a consecutive interval in the list, then clear the list and include the current node you are processing. At the end you should paint all nodes remaining in the list with the same color.

Rationale

We should partition the list in minimum amount of intervals such that all vertex within the same interval are not connected to any other vertex (they are an independent set). Since the first vertex in the list belong to an interval, this interval should start at this vertex. The proposed algorithm will find maximal interval containing this vertex. It is impossible to find any bigger interval containing the first vertex (since the one chosen is maximal) and it doesn't make any sense to find any smaller interval, since not taken vertex will only increase our restrictions in the future while taking next intervals.

Pseudocode

Graph := Relations between vertex. Graph[u] is the list of all neighbors of u
List := Order of vertex. List[1] = v1, List[2] = v2, etc...

S := {} (Set with all nodes in the interval we are keeping)
color := 0 (Number of colors used so far)

# Iterate through all vertex 
for vertex in List:

   # Check this node is not connected to any other node in S
   ok := True
   for neig in Graph[vertex]:
      if neig in S:
          ok := False
          break

   if ok:
       # If vertex is not neighbor of any other vertex in S, include it in.
       S.add(vertex)
   else:

       # Paint all vertex in S with color
       paint(S, color)

       # Increase color, since an interval of nodes was painted
       color += 1

       # Reset S, starting with current node.
       S := {vertex}


# Don't forget to paint last interval

# Paint all vertex in S with color
paint(S, color)

# Increase color, since an interval of nodes was painted
color += 1


Complexity and details

Notice in the implementation you don't need to maintain the set of taken nodes S explicitly, since all nodes in that set belong to an interval they can be easily represented with two pointer (the begin of the interval and the end of the interval). The overall complexity of this solution is $O(|V| + |E|)$, since every node is visited once in the first loop, and edges are traversed twice, one per endpoint. Regarding paint function, it is potentially linear in the number of vertex it is painting, but that is ok, since we paint each vertex exactly once.