In the INTERVALIZING COLOURED GRAPHS problem, one must decide for a given graph G = (V,E) with a proper vertex coloring of G whether G is the subgraph of a properly colored interval graph. For the case that the number of colors k is fixed, we give an exact algorithm that uses O*(2n/log1-e(n)) time for all e > 0. We also give an O*(2n) algorithm for the case that the number of colors k is not fixed.
['Hans L. Bodlaender', 'Johan M. M. van Rooij']
Exact algorithms for intervalizing colored graphs