An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
James B. Orlin, Maurizio A. Bonuccelli, Daniel Pierre Bovet · SIAM Journal on Algebraic and Discrete Methods · 1981
A graph is a circular arc graph if each vertex of the graph is associated with an arc on a circle in such a way that two vertices of the graph are adjacent if and only if the corresponding arcs overlap. A circular arc graph is proper if none of the representing arcs is contained within another. An $O(n^2 )$ algorithm is given for determining whether a proper circular arc graph with n nodes may be colored with k colors.