# Optimality of DSATUR on interval graphs

The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different colors among neighbours, total number of neighbours).

Though not always optimal, this algorithm is already known to be optimal on certain families of graphs, like cycles or bipartite graphs.

An interval graph is a non-directed graph $$G = (V, E)$$ such that there exists a set of intervals $$(I_v)_{v\in V}$$ such that $$\{u, v\}\in E\iff I_u\cap I_v\neq \emptyset$$.

My question is: is DSATUR optimal for interval graphs?

I already know that there are efficient optimal coloring algorithms for interval graphs, whether you know the corresponding interval set or not, but that is not the question.

My first intuition was that DSATUR was not always optimal, and as a tentative to find a counterexample, I tested 130 millions randomly generated interval graphs, of order between 10 and 20, but none was a counterexample.

That leads me to think that maybe it is optimal, but I have no real idea as to how to prove it.

As suggested by Juho in the comments, I tested the property for ALL interval graphs of order up to 12, and DSATUR is indeed optimal on those graphs.

• Is the ordering given by DSATUR not a perfect elimination ordering? If it can be shown that it is, the claim will follow from known results.
– Juho
Jul 13, 2021 at 13:03
• @Juho That's what I wondered, but I'm not so sure, since the first colored vertex would be the one of highest degree, and its neighbours are not necessarily a clique (for example if you consider a star). Jul 13, 2021 at 13:06
• I realize that the coloring algorithm for a chordal graph is the reverse of a perfect elimination ordering, so my counterexample is not a good one… That could be an idea. Jul 13, 2021 at 13:25
• Right, if you execute the greedy algorithm for a reverse peo, you will get an optimally properly colored chordal graph.
– Juho
Jul 13, 2021 at 13:44
• By the way, to find a counterexample, you could try all small interval graphs (see e.g., here for a list).
– Juho
Jul 14, 2021 at 10:54

Yes. DSATUR produces an optimal coloring for interval graphs. My idea is as follows (Please identify any potential issues). We know that a) In DSATUR, once a new vertex has been colored then we should determine which of the remaining uncolored vertices has the highest number of colors in its neighborhood to color this vertex next. b) For interval graphs a greedy coloring algorithm (by choosing the vertex ordering to be the reverse of a perfect elimination ordering) can be used to find an optimal coloring in polynomial time.

Theorem. By running the DSATUR algorithm, if we color the vertices of $$G=(V,E)$$ in order $$v_1,v_2,...,v_n$$ then we have a perfect elimination scheme $$v_n,v_{n-1},...,v_2,v_1$$ on $$G$$.

Proof. By induction. It is true for $$n=1,2,3$$. Suppose that it is true for $$n-1$$ and we want to prove it for $$n$$.

By removing $$v_n$$ to produce $$G'$$, all of vertices $$v_i$$ ($$i=n-1,...,1$$) are simplicial on $$G'$$ ($$v_i$$ is simplicial if all of its neighborhood $$v_j$$ where $$j induce a complete subgraph) and on $$G$$ and we have to prove this only for $$v_n$$.

If $$v_{n-1}v_n\notin E$$ then simplicial characteristic of $$v_n$$ is simply proved by removing the vertex $$v_{n-1}$$ to produce $$G'$$. Here, the order of coloring by DSATUR is unchanged and based on induction hypothesis, $$v_n$$ is simplicial on $$G'$$ and (due to $$v_{n-1}v_n\notin E$$) on $$G$$.

Suppose that $$v_{n-1}v_n\in E$$. If the vertex degree of $$v_n$$ is 1 then it is simplicial on $$G$$. Otherwise, suppose that $$v_t$$ ($$t) is the last vertex which is adjacent to $$v_n$$ and during the execution of DSATUR, after coloring of $$v_t$$ the DSATUR number of the vertex $$v_n$$ is $$k$$; i.e. After coloring of $$v_t$$ always there exist a vertex $$v_i$$ ($$t) with a DSATUR number greater than or equal to $$k$$.

Now remove $$v_t$$ to produce $$G'$$. By execution of DSATUR on $$G'$$ the order of coloring is unchanged until $$v_{t-1}$$ and after coloring of $$v_{t-1}$$, the DSATUR number of the vertex $$v_n$$ is $$k-1$$ and always there exist a vertex $$v_i$$ ($$t) with a DSATUR number greater than or equal to $$k-1$$; i.e. The vertex $$v_n$$ is the last colored vertex and the DSATUR algorithm colors the vertices of $$G'=(V-\{v_t\},E')$$ in order of $$v_1,...,v_{t-1},v_{i1},...,v_{it},v_n$$ where $$t. Therefore, based on the induction hypothesis $$v_n$$ is simplicial on $$G'$$.

We should prove that it is impossible to have $$v_{n-1}v_t\notin E$$ (Note that, if $$v_{n-1}v_t\in E$$ then $$v_n$$ is simplicial on $$G$$, too). Based on the above result $$v_{n-1}$$ is adjacent to all of neighborhoods of $$v_n$$ except to $$v_t$$. Then, suppose that the vertex degree of $$v_n$$ is greater than 2 and $$v_l$$ ($$l) is the last vertex which is adjacent to $$v_n$$ and during the execution of DSATUR, after coloring of $$v_l$$ the DSATUR number of the vertex $$v_n$$ is $$k-1$$; i.e. After coloring of $$v_l$$ always there exist a vertex $$v_i$$ ($$l) with a DSATUR number greater than or equal to $$k-1$$.

Now remove $$v_l$$ to produce $$G'$$. By execution of DSATUR on $$G'$$ the order of coloring is unchanged until $$v_{l-1}$$ and after coloring of $$v_{l-1}$$, the DSATUR number of the vertex $$v_n$$ is $$k-2$$ and always there exist a vertex $$v_i$$ ($$l) with a DSATUR number greater than or equal to $$k-2$$; i.e. The vertex $$v_n$$ is the last colored vertex and the DSATUR algorithm colors the vertices of $$G'=(V-\{v_l\},E')$$ in order of $$v_1,...,v_{l-1}, v_{i1},...,v_{il},v_n$$ where $$l. Therefore, based on the induction hypothesis $$v_n$$ is simplicial on $$G'$$ and we should have $$v_{n-1}v_t\in E$$.

Finally, suppose that the vertex degree of $$v_n$$ is equal to 2 and we cannot select such a vertex $$v_l$$ in the above proof. Hence, during the execution of the algorithm, the DSATUR number of $$v_n$$ is $$0$$ until coloring of vertex $$v_t$$ which increases the DSATUR number of $$v_n$$ to $$1$$. Then, there exist no common neighborhood for the vertices $$v_{n-1}$$ and $$v_t$$, due to the construction of a cycle with no chord. Moreover, There exist no common neighborhood for the neighborhoods of vertices $$v_{n-1}$$ and $$v_t$$, due to the construction of a cycle with no chord and so on. Therefore, the vertices $$v_t,v_{n-1}$$ and $$v_n$$ are (only) on some paths and by execution of DSATUR on these paths the vertex $$v_n$$ is colored between two vertices $$v_t$$ and $$v_{n-1}$$. Hence, it is impossible to have a coloring order $$v_1,...,v_t,...,v_{n-1},v_n$$ in DSATUR algorithm which is a contradiction.