Grafos de Intervalo

SOBRE ORDENS E GRAFOS DE INTERVALO

Fabiano de Souza Oliveira

Tese de Doutorado apresentada ao Programa de P´s-gradua¸˜o em Engenharia de o ca
Sistemas e Computa¸˜o, COPPE, da ca Universidade Federal do Rio de Janeiro, como parte dos requisitos necess´rios ` a a obten¸˜o do t´ ca ıtulo de Doutor em Engenharia de Sistemas e Computa¸˜o. ca Orientadores: Jayme Luiz Szwarcfiter
M´rcia Rosana Cerioli a Rio de Janeiro
Mar¸o de 2011 c SOBRE ORDENS E GRAFOS DE INTERVALO
Fabiano de Souza Oliveira

TESE SUBMETIDA AO CORPO DOCENTE DO INSTITUTO ALBERTO LUIZ
´
COIMBRA DE POS-GRADUACAO E PESQUISA DE ENGENHARIA (COPPE)
¸˜
DA UNIVERSIDADE FEDERAL DO RIO DE JANEIRO COMO PARTE DOS
´
REQUISITOS NECESSARIOS PARA A OBTENCAO DO GRAU DE DOUTOR
¸˜
ˆ
EM CIENCIAS EM ENGENHARIA DE SISTEMAS E COMPUTACAO.
¸˜
Examinada por:

Prof. Jayme Luiz Szwarcfiter, Ph.D.

Prof. M´rcia Rosana Cerioli, D.Sc. a Prof. Carlos Eduardo Ferreira, Dr. rer. nat.

Prof. C´lia Picinin de Mello, D.Sc. e Prof. Valmir Carneiro Barbosa, Ph.D.

RIO DE JANEIRO, RJ – BRASIL
MARCO DE 2011
¸

Oliveira, Fabiano de Souza
Sobre Ordens e Grafos de Intervalo/Fabiano de Souza
Oliveira. – Rio de Janeiro: UFRJ/COPPE, 2011.
XIII, 78 p.: il.; 29, 7cm.
Orientadores: Jayme Luiz Szwarcfiter
M´rcia Rosana Cerioli a Tese (doutorado) – UFRJ/COPPE/Programa de
Engenharia de Sistemas e Computa¸˜o, 2011. ca Referˆncias Bibliogr´ficas: p. 74 – 78. e a
1. Contagem de Intervalo. 2. Dimens˜o de Ordens. a 3. Grafos de Intervalo. 4. Interval Count. 5. Ordens de Cliques.
6. Ordens de Intervalo.
I. Szwarcfiter,
Jayme Luiz et al. II. Universidade Federal do Rio de
Janeiro, COPPE, Programa de Engenharia de Sistemas e
Computa¸˜o. III. T´ ca ıtulo.

iii

Dedicado a Cristiane, Melissa e
Olavo, por todo amor e compreens˜o. a

iv

Agradecimentos
Seria de se esperar que esta se¸˜o de agradecimentos fosse semelhante com a ca se¸˜o correspondente da disserta¸˜o de