Id: arxiv/2606.21640 Url: https://arxiv.org/abs/2606.21640 Tags: math.CO, cs.DM Score: 0 Title: The Twin-Width of Graphs of Bounded VC-Dimension Domain: math.CO Source: arxiv Authors: Therese Biedl, Taite LaGrange, Sophie Spirkl Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-19 Page: https://delphi.science/r/arxiv/2606.21640 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…