Coloring a Family of Circular Arcs

Abstract

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.