Graph classes with and without powers of bounded clique-width

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 characteriz...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Grippo, L.N., Milanič, M., Safe, M.D.
Formato: JOUR
Materias:
Clique-width
Hereditary graph class
Power of a graph
Power-bounded clique-width
Combinatorial mathematics
Forbidden induced subgraphs
Graph class
Induced subgraphs
Positive integers
Sufficient and necessary condition
Within class
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v199_n_p3_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_0166218X_v199_n_p3_Bonomo
record_format dspace
spelling todo:paper_0166218X_v199_n_p3_Bonomo2023-10-03T15:03:44Z Graph classes with and without powers of bounded clique-width Bonomo, F. Grippo, L.N. Milanič, M. Safe, M.D. Clique-width Hereditary graph class Power of a graph Power-bounded clique-width Combinatorial mathematics Clique-width Forbidden induced subgraphs Graph class Induced subgraphs Positive integers Power of a graph Sufficient and necessary condition Within class Graph theory 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. © 2015 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Grippo, L.N. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v199_n_p3_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Clique-width
Hereditary graph class
Power of a graph
Power-bounded clique-width
Combinatorial mathematics
Clique-width
Forbidden induced subgraphs
Graph class
Induced subgraphs
Positive integers
Power of a graph
Sufficient and necessary condition
Within class
Graph theory
spellingShingle Clique-width
Hereditary graph class
Power of a graph
Power-bounded clique-width
Combinatorial mathematics
Clique-width
Forbidden induced subgraphs
Graph class
Induced subgraphs
Positive integers
Power of a graph
Sufficient and necessary condition
Within class
Graph theory
Bonomo, F.
Grippo, L.N.
Milanič, M.
Safe, M.D.
Graph classes with and without powers of bounded clique-width
topic_facet Clique-width
Hereditary graph class
Power of a graph
Power-bounded clique-width
Combinatorial mathematics
Clique-width
Forbidden induced subgraphs
Graph class
Induced subgraphs
Positive integers
Power of a graph
Sufficient and necessary condition
Within class
Graph theory
description 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. © 2015 Elsevier B.V. All rights reserved.
format JOUR
author Bonomo, F.
Grippo, L.N.
Milanič, M.
Safe, M.D.
author_facet Bonomo, F.
Grippo, L.N.
Milanič, M.
Safe, M.D.
author_sort Bonomo, F.
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
url http://hdl.handle.net/20.500.12110/paper_0166218X_v199_n_p3_Bonomo
work_keys_str_mv AT bonomof graphclasseswithandwithoutpowersofboundedcliquewidth
AT grippoln graphclasseswithandwithoutpowersofboundedcliquewidth
AT milanicm graphclasseswithandwithoutpowersofboundedcliquewidth
AT safemd graphclasseswithandwithoutpowersofboundedcliquewidth
_version_ 1807321033333538816

Ejemplares similares