A complexidade do reconhecimento de grafos k-fino próprio de precedência
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.
Oliveira, F. S., Sampaio Jr., M. S., and Szwarcfiter, J. L. (2018). Sobre finura própria de grafos. In Anais do III Encontro de Teoria da Computação. SBC.
Roberts, F. (1969). Indifference graphs. In Harary, F., editor, Proof Techniques in Graph Theory, pages 139–146. Academic Press, New York.
Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC’78, pages 216–226.