Coloring a Family of Circular Arcs
Alan C. Tucker · SIAM Journal on Applied Mathematics · 1975
This paper presents a collection of results about coloring a family of circular arcs. We prove that the strong perfect graph conjecture is valid for circular-arc graphs. We give some upper bounds on the number of colors needed to color various families of arcs. Finally, we convert the problem of determining whether a family of arcs can be q-colored into a multicommodity flow problem.