Thinness of product graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2022-05, Vol.312, p.52-71
Main Authors: Bonomo-Braberman, Flavia, Gonzalez, Carolina L., Oliveira, Fabiano S., Jr, Moysés S. Sampaio, Szwarcfiter, Jayme L.
Format: Article
Language:English
Subjects:
Complete thinness
Graph operations
Graphical representations
Graphs
Independent thinness
Polynomials
Product graphs
Proper thinness
Thinness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2021.04.003