Abstract
A circular-arc family F is a collection of arcs on a circle. Such a family is said to be proper if no arc is contained within another. The coloring problem on circular-arc families has been shown to be NP-hard by Garey, Johnson, Miller and Papadimitriou. However, on proper circular-arc families, the coloring problem was shown to be solvable originally in O(n 2 logn) time by Orlin et al. and later, in O(n 1.5 logn) time by Teng and Tucker. Their approach is to transform the (q-colorability) problem of testing whether G is q-colorable into a shortest path problem and, then, to apply binary search to solve log n q-colorability problems. In this note we show that Teng and Tucker's algorithm can be implemented to run in O(n 1.5 ) time overall using an interesting relationship between the time it takes to solve a q-colorability problem and the range of possible q to be searched for. © 1989.