Combinatorics and Graph Theory

Graph Thinness, a Lower Bound and Complexity

Authors: Yaroslav Shitov
Comments: 9 pages

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,...,V_k) such that, for all u, v, w in V with u<v<w, if u and v belong to the same class and {u,w} is in E, then {v,w} is in E. We prove that (1) there are $n$-vertex graphs of thinness $n-o(n)$, which answers a question of Bonomo-Braberman, Gonzalez, Oliveira, Sampaio, and Szwarcfiter, (2) the computation of thinness is NP-hard, which is a solution to a long standing open problem posed by Mannino and Oriolo.
Category: Combinatorics and Graph Theory