The intersection between some subclasses of circular-arc and circle graphs

GRAVANO, AGUSTIN; DURAN, GUILLERMO ALFREDO

CONGRESSUS NUMERANTIUM

Año: 2002 vol. 159 p. 183 - 192

0384-9864

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. The intersection graph of a family of chords in a circle is called a circle graph. analogously, this class of graphs admits some subclasses too: proper circular-arc graphs, unit circle graphs, Helly circle graphs and clique-Helly circle graphs. In this paper, all possible intersections of these subclasses are studied. After eliminating trivially empty regions, twenty six regions remain. Two of them are empty as a consequence of a theorem by Durán and Lin. Twenty three regions are non-empty and we construct a minimal graph in each of them. Our main result is that the twenty-sixth region is empty, namely we prove that if a graph is Helly circle and unit circle, then it is also a Helly circular-arc graph. Finally, we show that all the trees are included in three of these regions and present an efficient algorithm to classify them.