INVESTIGADORES
BONOMO Flavia
artículos
Título:
Thinness of product graphs
Autor/es:
BONOMO-BRABERMAN, FLAVIA; GONZALEZ, CAROLINA L.; OLIVEIRA, FABIANO S.; JR., MOYSÉS S. SAMPAIO; SZWARCFITER, JAYME L.
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2022 vol. 312 p. 52 - 71
ISSN:
0166-218X
Resumen:
The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph.In this paper we study the thinness and its variations of graph products. We show that the thinness behaves "well" in general for products, in the sense that for most of the graph products defined in the literature, the thinness of the product of two graphs is bounded by a function (typically product or sum) of their thinness, or of the thinness of one of them and the size of the other. We also show for some cases the non-existence of such a function.
