2025/04/03 by Irene Heinrich, Heinrich, Irene, Ferdinand Ihringer +5
Mathematics · #68Q25 #68R05 #68R10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #G.2.1 #G.2.2 #Graph theory and applications #Rings, Modules, and Algebras
paper · pdf · doi:10.48550/arxiv.2504.02342
openalex publication_date 2025/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Twin-width is a recently introduced graph parameter based on the repeated contraction of near-twins. It has shown remarkable utility in algorithmic and structural graph theory, as well as in finite model theory -- particularly since first-order model checking is fixed-parameter tractable when a witness certifying small twin-width is provided. However, the behavior of twin-width in specific graph classes, particularly cubic graphs, remains poorly understood. While cubic graphs are known to have unbounded twin-width, no explicit cubic graph of twin-width greater than 4 is known. This paper explores this phenomenon in regular and near-regular graph classes. We show that extremal graphs of bounded degree and high twin-width are asymmetric, partly explaining their elusiveness. Additionally, we establish bounds for circulant and d-degenerate graphs, and examine strongly regular graphs, which exhibit similar behavior to cubic graphs. Our results include determining the twin-width of Johnson graphs over 2-sets, and cyclic Latin square graphs.