On the domatic number of interval graphs (Q1111388)

A dominating set of a graph G is a subset S of the nodes such that every node of G is either in S or adjacent to some node in S. The domatic number of G is the size of a maximum cardinality partition of the nodes into dominating sets. We present an \(O(n^{2.5})\) time algorithm for finding the domatic number, as well as the desired partition, of an interval graph (which is a graph representing intersecting intervals on the real line). We also give an O(n log n) time algorithm for proper interval graphs (graphs for which no interval is properly contained within another).