Graph classes with and without powers of bounded clique-width | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | University Of Primorska | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Grippo, Luciano Norberto | |
| dc.contributor.author | Milanič, Martin | |
| dc.contributor.author | Safe, Martin Dario | |
| dc.date.issued | 2016-01 | |
| dc.description.abstract | We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and ℓ such that the kth powers of the graphs are of clique-width at most ℓ. We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer k, there exists a graph class such that the kth powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas ; Argentina | |
| dc.description.fil | Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Milanič, Martin. University Of Primorska; Eslovenia | |
| dc.description.fil | Fil: Safe, Martin Dario. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de General Sarmiento; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Grippo, Luciano Norberto; Milanič, Martin; Safe, Martin Dario; Graph classes with and without powers of bounded clique-width; Elsevier Science; Discrete Applied Mathematics; 199; 1-2016; 3-15 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/55546 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 3-15 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 199 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2015.06.010 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X15002966 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | Clique-Width | es |
| dc.subject | Hereditary Graph Class | es |
| dc.subject | Power of A Graph | es |
| dc.subject | Power-Bounded Clique-Width | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Matemática Pura | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Graph classes with and without powers of bounded clique-width | 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.0138e4a5-ed05-4ce7-b84c-23c32bd5445e_A.pdf
- Tamaño:
- 889.78 KB
- Formato:
- Adobe Portable Document Format