On intervalizing k-colored graphs for DNA physical mapping Original Research Article

The problem of determining whether a given k-colored graph is a subgraph of a properly colored interval graph has an application in DNA physical mapping. In this paper, we study the problem for the case that the number of colors k is fixed. For k = 2, we give a simple linear time algorithm, for k = 3, we give an O(n2) algorithm for biconnected graphs with n vertices, and for k = 4, we show that the problem is NP-complete.