On Intersection Graphs of Arcs and Chords in a Circle

Resumen

Tesis de Doctorado en Ciencias de la ComputaciónTitle: On intersection graphs of arcs and chords in a circleGuillermo A. DuránDate: May 19 th., 2000Departamento de Computación - FCEyN – UBAAdvisor: Jayme L. Szwarcfiter (UFRJ)Abstract:Circular-arc graphs are the intersection graphs of arcs on a circle. We review in this thesisthe main results known about this class and we analize some subclasses of it. We show newcharacterizations for proper circular-arc graphs derived from a characterization formulatedby Tucker, and we deduce minimal forbidden structures for circular arc-graphs.All possible intersections of the defined subclasses are studied, showing a minimal examplein each one of the generated regions, except one of them that we prove it is empty. Fromhere, we conclude that a clique-Helly and proper no unit circular-arc graph must be Hellycircular-arc graph.Circle graphs are the intersection graphs of chords in a circle. We present also a review ofthe main results in this class and define the most important subclasses, proving somerelations of inclusions between them.We prove a neccesary condition so that a graph is a Helly circle graph and conjecture thatthis condition is sufficient too. If this conjecture becomes true, we would have acharacterization and a polynomial recognition for this subclass.Minimal forbidden structures for circle graphs are shown, using the chacterization of propercircular-arc graphs by Tucker and a characterization theorem for circle graphs by Bouchet.We also analize all the possible intersections between the defined subclasses of circlegraphs, showing a minimal example in each generated region.A superclass of circle graphs is studied: overlap graphs of circular-arc graphs. We shownew properties on this class, analizing its relation with circle and circular-arc graphs. Anecessary condition for a graph being an overlap graph of circular-arc graphs is shown.We prove that the problem of finding a minimum clique partition for the class of graphswhich does not contain either odd holes, or a 3-fan, or a 4-wheel as induced subgraphs, canbe solved in polynomial time. We use in the proof results of polyhedral theory for integerlinear programming. We extend this result for minimum clique covering by vertices. Theseresults are applied for Helly circle graphs without odd holes.We also show that the problem of minimum clique covering by vertices can be solved inpolynomial time for Helly circular-arc graphs.Finally, we present some interesting problems which remain open.