Sobre Finura Própria de Grafos

• Moysés S. Sampaio Jr.
• Fabiano S. Oliveira
• Jayme L. Szwarcfiter

DOI: https://doi.org/10.5753/etc.2018.3165

Resumo

Both graph classes of k-thin and proper k-thin graphs have recently been introduced generalizing interval and unit interval graphs, respectively. The complexity of the recognition of k-thin and proper k-thin are open, even for fixed k 2. In this work, we introduce a subclass of the proper 2-thin graphs, called proper 2-thin of precedence. For this class, we present a characterization and an efficient recognition algorithm.