info:eu-repo/semantics/article
Normal Helly circular-arc graphs and its subclasses
Fecha
2013-05Registro en:
Lin, Min Chih; Soulignac, Francisco Juan; Szwarcfiter, Jayme L.; Normal Helly circular-arc graphs and its subclasses; Elsevier Science; Discrete Applied Mathematics; 161; 7-8; 5-2013; 1037-1059
0166-218X
CONICET Digital
CONICET
Autor
Lin, Min Chih
Soulignac, Francisco Juan
Szwarcfiter, Jayme L.
Resumen
A Helly circular-arc model M=(C,A) is a circle C together with a Helly family A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a unit Helly circular-arc model, and if there are no two arcs covering the circle, then M is a normal Helly circular-arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc graph is the intersection graph of the arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc model. In this article we study these subclasses of Helly circular-arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly circular-arc subclasses. Next, we describe characterizations for the subclasses of Helly circular-arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how these classes of graphs relate with straight and round digraphs.
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
Duran, Guillermo Alfredo; Grippo, Luciano Norberto; Safe, Martin Dario (Elsevier Science, 2014-02)Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous ... -
Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
Autor desconocido (NORTH HOLLAND, 2014) -
Partial characterizations of clique-perfect graphs ii: diamond-free and helly circular-arc graphs
Autor desconocido (ELSEVIER SCIENCE BV, 2009)