An approximation algorithm for coloring circular-arc graphs
Wen-Chieh Shih, Wen−Lian Hsu · 1990
Consider families of arcs on a circle. The minimum coloring problem on arc families has been shown to be NP-hard by Garey, Johnson, Miller and Papadimitriou. It is easy to show that 2q colors are sufficient for any arc family F, where q is the size of a maximum clique in F and 3q/2 colors are necessary for some families. It has long been open problem to find a coloring algorithm which uses no more than α·q colors, where α is strictly less than 2. In this paper we present such an algorithm with α=5/3. Our algorithm is based on: (1) an extension of an earlier result of Tucker on coloring special families and (2) a characterization of the existence of perfect matching in bipartite graphs.