Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Few days ago I was working on interval graphs to solve the known problem of resource allocation, as we know there is a greedy approach that solves this problem (chromatic number) in polynomial time and gives us the colors of each vertex in the interval graph (the problem of finding the chromatic number in general graphs is NP-Complete (3-satisfiability reduction by Karp)).

I was wondering: if had a graph that is not an interval graph but it is because it has one and only one chordless cycle of length > 3 (there is an edge that, when you remove it, the graph becomes an interval graph), does it makes the problem of finding the chromatic number on this kind of graph NP-Complete?

share|cite|improve this question
Cross-post from SO:… – Peter Taylor Jan 22 '11 at 19:39
up vote 13 down vote accepted

I believe these graphs can be colored in polynomial time. Moron has already provided a reference, but here's an explicit algorithm.

Suppose that $G-uv$ is an interval graph, for edge $uv$, and form an interval representation for it. We can assume without loss of generality that no two intervals have the same endpoint. We can also assume without loss of generality that $u$ and $v$ are the two extreme intervals; for, if some other interval were extreme, we could remove it, optimally color the resulting smaller graph (also of the form interval+one edge), and then optimally extend the coloring to the removed vertex (because its neighborhood is a clique).

So the remaining question is: does $G-uv$ have an optimal coloring in which $u$ and $v$ have different colors, or does edge $uv$ require us to use one more color? But this is easily solved by a dynamic program on the subintervals of the interval representation.

In more detail, for subinterval $i$ let $C[i]$ denote the set of intervals (vertices of G) that cover that subinterval, let $D[i]$ be a Boolean value, true if there exists a coloring of the subinterval (in an optimal coloring of $G-uv$) that does not use the same color as $u$, and let $E[i]$ be the set of vertices that can be colored with the same color as $u$ (again, in an optimal coloring). As a base case, $C[0]=E[0]=\{u\}$ and $D[0]$ is false. When going from subinterval $i$ to subinterval $i+1$, across the right endpoint of an interval $w$, we set $D$ to be the disjunction of its old value and the predicate $w\in E[i]$, and we then remove $w$ from $C[i]$ and $E[i]$. When going across the left endpoint of an interval $w$, we add $w$ to $C[i]$, we add it to $E[i]$ if $D$ is true, and we change $D$ from true to false if the new size of $C[i]$ equals the number of colors in an optimal coloring of $G-uv$.

Then, the optimal number of colors of $G$ is the same as for $G-uv$ iff either D is true for the final subinterval, or E[i] has more than one member in the final subinterval. Otherwise, the optimal number of colors for $G$ is one plus the optimal number of colors for $G-uv$.

share|cite|improve this answer
Love the algorithm; i formally demonstrate its correctness and works great, thanks – David Darias Jan 25 '11 at 4:40

According this here: (see slides 14 and 15)

For fixed $k$, for the class of graphs formed by adding $k$ edges to interval graphs, the chromatic number problem is in P.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.