Finding a Domatic Partition of an Interval Graph in Time $O(n)$
Glenn K. Manacher, Terrance A. Mankus · SIAM Journal on Discrete Mathematics · 1996
We present a simple $O(n)$ time and space algorithm for producing a domatic partition and the domatic number for members of the class of interval graphs, where n is the number of intervals in a graph.