A complexidade do reconhecimento de grafos k-fino próprio de precedência - Bonomo-Braberman, Flavia; Oliveira, Fabiano; Sampaio Jr., Moysés; Szwarcfiter, Jayme (Anais do Encontro de Teoria da Computação (ETC), 2020)
The class of precedence proper k-thin graphs is a subclass of proper k-thin graphs. The complexity status of recognizing proper k-thin graphs is unknown for any fixed k ≥ 2. In this work, we prove that, when k is part of the input, the problem of recognizing precedence proper k-thin graphs is NP-complete, and we present a characterization for them based on threshold graphs.