Mostrar el registro sencillo del ítem
dc.contributor.author
Safe, Martin Dario
dc.date.available
2022-07-08T15:40:13Z
dc.date.issued
2022-10-30
dc.identifier.citation
Safe, Martin Dario; Essential obstacles to Helly circular-arc graphs; Elsevier Science; Discrete Applied Mathematics; 320; 30-10-2022; 245-258
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/161720
dc.description.abstract
A Helly circular-arc graph is the intersection graph of a set of arcs on a circle having the Helly property. We introduce essential obstacles, which are a refinement of the notion of obstacles, and prove that essential obstacles are precisely the minimal forbidden induced circular-arc subgraphs for the class of Helly circular-arc graphs. We show that it is possible to find in linear time, in any given obstacle, some minimal forbidden induced subgraph for the class of Helly circular-arc graphs contained as an induced subgraph. Moreover, relying on an existing linear-time algorithm for finding induced obstacles in circular-arc graphs, we conclude that it is possible to find in linear time an induced essential obstacle in any circular-arc graph that is not a Helly circular-arc graph. The problem of finding a forbidden induced subgraph characterization, not restricted only to circular-arc graphs, for the class of Helly circular-arc graphs remains unresolved. As a partial answer to this problem, we find the minimal forbidden induced subgraph characterization for the class of Helly circular-arc graphs restricted to graphs containing no induced claw and no induced 5-wheel. Furthermore, we show that there is a linear-time algorithm for finding, in any given graph that is not a Helly circular-arc graph, an induced subgraph isomorphic to claw, 5-wheel, or some minimal forbidden induced subgraph for the class of Helly circular-arc graphs.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
CIRCULAR-ARC GRAPHS
dc.subject
FORBIDDEN SUBGRAPHS
dc.subject
HELLY PROPERTY
dc.subject
CLAW-FREE GRAPHS
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Essential obstacles to Helly circular-arc graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2022-07-04T19:15:32Z
dc.journal.volume
320
dc.journal.pagination
245-258
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Safe, Martin Dario. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Matemática Bahía Blanca. Universidad Nacional del Sur. Departamento de Matemática. Instituto de Matemática Bahía Blanca; Argentina
dc.journal.title
Discrete Applied Mathematics
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://doi.org/10.1016/j.dam.2022.04.024
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/arxiv/https://arxiv.org/abs/1612.01513
Archivos asociados