Sobre Finura Própria de Grafos

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

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.

Publicado
26/07/2018
SAMPAIO JR., Moysés S.; OLIVEIRA, Fabiano S.; SZWARCFITER, Jayme L.. Sobre Finura Própria de Grafos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3165.