Normal Helly circular-arc graphs and its subclasses

dc.creatorLin, Min Chih
dc.creatorSoulignac, Francisco Juan
dc.creatorSzwarcfiter, Jayme L.
dc.date.accessioned2019-09-25T19:08:11Z
dc.date.accessioned2022-10-15T02:15:55Z
dc.date.available2019-09-25T19:08:11Z
dc.date.available2022-10-15T02:15:55Z
dc.date.created2019-09-25T19:08:11Z
dc.date.issued2013-05
dc.identifierLin, 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
dc.identifier0166-218X
dc.identifierhttp://hdl.handle.net/11336/84437
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/4334131
dc.description.abstractA 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.
dc.languageeng
dc.publisherElsevier Science
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2012.11.005
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X12004295
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.subjectHELLY CIRCULAR-ARC GRAPHS
dc.subjectNORMAL CIRCULAR-ARC GRAPHS
dc.subjectPROPER CIRCULAR-ARC GRAPHS
dc.subjectUNIT CIRCULAR-ARC GRAPHS
dc.titleNormal Helly circular-arc graphs and its subclasses
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución