Graph thinness: a lower bound and complexity
Yaroslav Nikolaevich Shitov · Pacific Journal of Mathematics · 2025
SHITOVThe thinness of a simple graph G = (V, E) is the smallest integer k for which there exist a total order (V, <) and a partition of V into k classes (V 1 , . . ., V k ) such that, for all u, v, w ∈ V with u < v < w, if u, v belong to the same class and {u, w} ∈ E, then {v, w} ∈ E. We prove:• There are n-vertex graphs of thinness n-o(n), which answers a question of Bonomo-Braberman, Gonzalez, Oliveira, Sampaio, and Szwarcfiter.• The computation of thinness is NP-hard, which is a solution to a longstanding open problem posed by Mannino and Oriolo.Problem 1 (GRAPH THINNESS).Given: A simple graph G = (V, E), a positive integer k.Question: Do there exist• a total ordering < of the vertex set V and MSC2020: 05C85, 68Q17.