2023/09/11 by Kajal Das, Das, Kajal
Computer Science · Mathematics · #05C30 #05C38 #05C76 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2309.05297
openalex publication_date 2023/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Twin-width is a recently introduced graph parameter for finite graphs. It is an open problem to determine whether there is an n-vertex graph having twin-width at least n/2 (due to J. Ahn, K. Hendrey, D. Kim and S. Oum). In an earlier paper, the author showed that such a graph with less than equal to 5 vertices does not exist. In this article, we show that such a graph with 6 vertices does not exist. More precisely, we prove that each graph with 6 vertices has twin-width less than equal to 2.