Parallel algorithms to color interval graphs

Question

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?

Answer 1

I'm not really familiar with the topic, but with some searching there are some results.

For example, Efficient parallel algorithms on interval graphs by Das and Chen, and A simple optimal parallel algorithm for the minimum coloring problem on interval graphs by Yu and Yang both gave an algorithm with $O(\log n)$ time and $O(n)$ processors on the EREW PRAM model. Even for the chordal graphs (which is a superclass of the interval graphs) there is an algorithm with $O(\log^2 n)$ time and $O(n)$ processors on the CRCW PRAM model, in the paper Efficient parallel algorithms for chordal graphs by Klein. Maybe you can take a look at the papers and references, to make sure if there are any additional assumptions, like whether the interval representations are given or not.