Bounds on the Twin-Width of Product Graphs

DOI10.46298/DMTCS.10091arXiv2202.11556OpenAlexW4379093231MaRDI QIDQ6131799

Author name not available (Why is that?)

Publication date: 18 April 2024

Published in: (Search for Journal in Brave)

Abstract: 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 $GstarH$ 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.

Full work available at URL: https://arxiv.org/abs/2202.11556

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Bounds on the Twin-Width of Product Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131799)