Summary: 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 \(0(n^ 2\log n)\) time by Orlin et. al. and later, in \(0(n^{1.5}\log n)\) 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. We show that Teng and Tucker’s algorithm can be implemented to run in \(0(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.