Abstract:In this paper, we investigate which hereditary classes of graphs admit sub-linear (in the number of vertices) bounds on twin-width. By modifying conference graphs, we can show that split, bipartite, and co-bipartite graphs can all have linear twin-width. However, excluding an induced subgraph of each of these three types is equivalent to the class of graphs having bounded VC-dimension, as shown by Bousquet, Lagoutte, Li, Parreau and Thomassé. Graphs of bounded VC-dimension can have unbounded twin-width, but whether it can be linear was an open question. In this paper, we first present a tool for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods. Then, using this tool, we prove that graphs with bounded VC-dimension have twin-width at most sub-linear. We also obtain a separate, tighter upper bound for the class of interval graphs, as well as a lower bound.
From: Taite LaGrange [view email]
[v1]
Fri, 19 Jun 2026 17:48:49 UTC (44 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。