On some subclasses of circular-arc graphs
Guillermo Durán · 2002
Abstract: The intersection graph of a family of arcs on a circle is called a circular-arc graph. This class of graphs admits some interesting subclasses: proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and clique-Helly circular-arc graphs. In this paper, all possible intersections of these subclasses are studied. There are thirteen regions. Twelve of these are nonempty, and we construct a minimal graph in each of them. Our main result is that the thirteenth region is empty, namely we prove that among proper but no unit circular-arc graphs, every clique-Helly circular-arc graph is also a Helly circular-arc graph.