Essential obstacles to Helly circular-arc graphs | ||
| dc.conicet.organizacion | 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 | |
| dc.contributor.author | Safe, Martin Dario | |
| dc.date.issued | 2022-10-30 | |
| 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. | es |
| 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.format | application/pdf | es |
| dc.identifier.citation | Safe, Martin Dario; Essential obstacles to Helly circular-arc graphs; Elsevier Science; Discrete Applied Mathematics; 320; 30-10-2022; 245-258 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/161720 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 245-258 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 320 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| 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 | |
| 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 | es |
| dc.subject | FORBIDDEN SUBGRAPHS | es |
| dc.subject | HELLY PROPERTY | es |
| dc.subject | CLAW-FREE GRAPHS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Essential obstacles to Helly circular-arc graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.fbaca77d-5a58-45a5-b03b-ceec4a946502_A.pdf
- Tamaño:
- 455.84 KB
- Formato:
- Adobe Portable Document Format