Several NP-hard graph problems get easy if we consider interval graphs. There is a greedy algorithm to color optimally an interval graph. Just sort the intervals according their left endpoints and color each interval with the last freed color.
Every coloring algorithm especially every efficient parallel algorithm I see, use the endpoints of intervals to get an optimal coloring. With "efficient parallel" I mean that the problem is in the complexity class NC.
There is a possibility to use only the structure of the graph to color the interval graph but this uses a maximum matching in a bipartite graph which isn't known to be in NC.
Is there any efficient parallel algorithm that doesn't use the endpoints of the intervals and just uses the structure of the graph to color an interval graph?