Graph thinness: a lower bound and complexity

Yaroslav Shitov

Vol. 339 (2025), No. 2, 333–343

DOI: 10.2140/pjm.2025.339.333

Abstract

The 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,\dots <!--FUNCTION\; APPLICATION-->,V_k)$ such that, for all $u,v,w\in V$ with $u<v<w$, if $u,v$ belong to the same class and $\{u,w\}\in E$, then $\{v,w\}\in 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.

Keywords

interval graph, $k$-thin graph, NP-completeness

Mathematical Subject Classification

Primary: 05C85, 68Q17

Milestones

Received: 5 February 2025

Revised: 18 August 2025

Accepted: 20 August 2025

Published: 21 September 2025