Sobre Finura Própria de Grafos
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.
Referências
Bonomo, F., Estrada, D. (2017). On the thinness and proper thinness of a graph. CoRR, abs/1704.00379.
Mannino, C., Oriolo, G., Ricci, F.„ Chandran, S. (2007). The stable set problem and the thinness of a graph. Operations Research Letters, 35:1–9.
Olariu, S. (1991). An optimal greedy heuristic to color interval graphs. Information Processing Letters, 37:21–25.
Roberts, F. (1969). Indifference graphs. Em Harary, F., editor, Proof Techniques in Graph Theory, p. 139–146. Academic Press, New York.
Mannino, C., Oriolo, G., Ricci, F.„ Chandran, S. (2007). The stable set problem and the thinness of a graph. Operations Research Letters, 35:1–9.
Olariu, S. (1991). An optimal greedy heuristic to color interval graphs. Information Processing Letters, 37:21–25.
Roberts, F. (1969). Indifference graphs. Em Harary, F., editor, Proof Techniques in Graph Theory, p. 139–146. Academic Press, New York.
Publicado
26/07/2018
Como Citar
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
.
p. 117-120.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3165.
