Bounds on the Twin-Width of Product Graphs

Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomass\'{e} & Watrigant. Given two graphs $G$ and $H$ and a graph product $\star$, we address the question: is the twin-width of $G\star H$ bounded by a function of the twin-widths of $G$ and $H$ and their maximum de...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2023-01, Vol.25:1 (Graph Theory), p.1-24
Main Authors: Pettersson, William, Sylvester, John
Format: Article
Language:English
Subjects:
05c99, 68r10
computer science - discrete mathematics
g.2.2
Graphs
mathematics - combinatorics
Tensors
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomass\'{e} & Watrigant. Given two graphs $G$ and $H$ and a graph product $\star$, we address the question: is the twin-width of $G\star H$ bounded by a function of the twin-widths of $G$ and $H$ and their maximum degrees? It is known that a bound of this type holds for strong products (Bonnet, Geniet, Kim, Thomass\'{e} & Watrigant; SODA 2021). We show that bounds of the same form hold for Cartesian, tensor/direct, corona, rooted, replacement, and zig-zag products. For the lexicographical product it is known that the twin-width of the product of two graphs is exactly the maximum of the twin-widths of the individual graphs (Bonnet, Kim, Reinald, Thomass\'{e} & Watrigant; IPEC 2021). In contrast, for the modular product we show that no bound can hold. In addition, we provide examples showing many of our bounds are tight, and give improved bounds for certain classes of graphs.
ISSN:1365-8050
1365-8050
DOI:10.46298/dmtcs.10091