Graph classes with and without powers of bounded clique-width

Mostrar todas las versiones(2)

Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina.

Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Grippo, Luciano Norberto, Milanič, Martin, Safe, Martín D.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: Elsevier Science BV 2024
Materias:
Clique-width
Power of a graph
Hereditary graph class
Power-bounded clique-width
Ciencias de la Computación
Ciencias de la Computación e Información
Matemática Pura
Acceso en línea:http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1581
Aporte de:
Repositorio Institucional Digital de Acceso Abierto (UNGS) de Universidad Nacional de General Sarmiento
id I71-R177-UNGS-1581
record_format dspace
spelling I71-R177-UNGS-15812024-07-23T17:26:23Z Graph classes with and without powers of bounded clique-width Bonomo, Flavia Grippo, Luciano Norberto Milanič, Martin Safe, Martín D. Clique-width Power of a graph Hereditary graph class Power-bounded clique-width Ciencias de la Computación Ciencias de la Computación e Información Matemática Pura Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil: Safe, Martín D. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Milanič, Martin. Universidad de Primorska; Eslovenia. 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 cliquewidth 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. 2024-07-16T17:07:05Z 2024-07-16T17:07:05Z 2016 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion Bonomo, F., Grippo, L. N., Milanič, M. y Safe, M. (1-2016). Graph classes with and without powers of bounded clique-width. Discrete Applied Mathematics, (199), 3-15 0166-218X http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1581 eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Science BV Discrete Applied Mathematics. 1-2016; (199): 3-15 http://www.sciencedirect.com/science/article/pii/S0166218X15002966
institution Universidad Nacional de General Sarmiento
institution_str I-71
repository_str R-177
collection Repositorio Institucional Digital de Acceso Abierto (UNGS)
language Inglés
orig_language_str_mv eng
topic Clique-width
Power of a graph
Hereditary graph class
Power-bounded clique-width
Ciencias de la Computación
Ciencias de la Computación e Información
Matemática Pura
spellingShingle Clique-width
Power of a graph
Hereditary graph class
Power-bounded clique-width
Ciencias de la Computación
Ciencias de la Computación e Información
Matemática Pura
Bonomo, Flavia
Grippo, Luciano Norberto
Milanič, Martin
Safe, Martín D.
Graph classes with and without powers of bounded clique-width
topic_facet Clique-width
Power of a graph
Hereditary graph class
Power-bounded clique-width
Ciencias de la Computación
Ciencias de la Computación e Información
Matemática Pura
description Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina.
format Artículo
Artículo
publishedVersion
author Bonomo, Flavia
Grippo, Luciano Norberto
Milanič, Martin
Safe, Martín D.
author_facet Bonomo, Flavia
Grippo, Luciano Norberto
Milanič, Martin
Safe, Martín D.
author_sort Bonomo, Flavia
title Graph classes with and without powers of bounded clique-width
title_short Graph classes with and without powers of bounded clique-width
title_full Graph classes with and without powers of bounded clique-width
title_fullStr Graph classes with and without powers of bounded clique-width
title_full_unstemmed Graph classes with and without powers of bounded clique-width
title_sort graph classes with and without powers of bounded clique-width
publisher Elsevier Science BV
publishDate 2024
url http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1581
work_keys_str_mv AT bonomoflavia graphclasseswithandwithoutpowersofboundedcliquewidth
AT grippolucianonorberto graphclasseswithandwithoutpowersofboundedcliquewidth
AT milanicmartin graphclasseswithandwithoutpowersofboundedcliquewidth
AT safemartind graphclasseswithandwithoutpowersofboundedcliquewidth
_version_ 1817375049055731712

Ejemplares similares