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

<p>For example, <a href="http://www.springerlink.com/content/y2246h381337w01t/">Efficient parallel algorithms on interval graphs</a> by Das and Chen, and <a href="http://www.sciencedirect.com/science/article/pii/002001909390267D">A simple optimal parallel algorithm for the minimum coloring problem on interval graphs</a> 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 <a href="http://www.cs.brown.edu/research/pubs/pdfs/1996/Klein-1996-EPA.pdf">Efficient parallel algorithms for chordal graphs</a> 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.</p>

CC BY-SA 3.0
2011-06-17T12:52:33.450Z
Thank you for the good references. I know the first two papers and they use the interval representations to color the graph. I think the last paper is what I'm looking for.
Marc Bury
CC BY-SA 3.0
2011-06-17T02:36:42.250Z
2011-06-17T02:36:42.250Z
Hsien-Chih Chang 張顯之
<p>Several NP-hard graph problems get easy if we consider <a href="http://en.wikipedia.org/wiki/Interval_graph">interval graphs</a>. 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.</p>

<p>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. </p>

<p>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.</p>

<p>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?</p>

<ds.algorithms><graph-algorithms><dc.parallel-comp><graph-colouring>
Parallel algorithms to color interval graphs
Marc Bury
# Parallel algorithms to color interval graphs

(Asked by: username_0 on 2011-06-17)

Several NP-hard graph problems get easy if we consider [interval graphs](http://en.wikipedia.org/wiki/Interval_graph). 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?

**Tags:** ds.algorithms, graph-algorithms, dc.parallel-comp, graph-colouring

---

## 1 answers

### Answer by username_1 on 2011-06-17. Score: 6 | Accepted answer

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

For example, [Efficient parallel algorithms on interval graphs](http://www.springerlink.com/content/y2246h381337w01t/) by Das and Chen, and [A simple optimal parallel algorithm for the minimum coloring problem on interval graphs](http://www.sciencedirect.com/science/article/pii/002001909390267D) 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](http://www.cs.brown.edu/research/pubs/pdfs/1996/Klein-1996-EPA.pdf) 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.

> **Comments:**
> **username_0**: Thank you for the good references. I know the first two papers and they use the interval representations to color the graph. I think the last paper is what I'm looking for.  

---

