Um problema extremal em contagem de intervalo

• Ano de defesa: 2018
• Autor(a) principal: Medeiros, Lívia Salgado
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; BR; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Extremal Problem; Interval Count; Interval Graphs; Interval Orders; Split Graph; Trivially Perfect Graph; Contagem de Intervalo; Grafos de Intervalo; Grafo de Divisão; Grafo Trivialmente Perfeito; Ordens de Intervalo; Problema Extremal; Teoria dos grafos; Algoritmos; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/7660

Esta dissertação apresenta um estudo sobre o problema da contagem de intervalo para grafos e ordens de intervalo. A contagem de intervalo de um dado grafo (resp. ordem) é o menor número de tamanhos de intervalo necessário em um modelo deste grafo (resp.ordem). No primeiro instante, a pesquisa foi direcionada a uma revisão da literatura sobre o problema da contagem de intervalo e seus principais resultados. Em seguida, tratamos do problema extremal que consiste em determinar o menor grafo ou ordem que possui a contagem de intervalo igual a dado natural k. Em particular, estudamos uma conjectura acerca deste problema extremal, verificando sua validade quando restrita às classes das ordens trivialmente perfeitas e de divisão. São apresentados resultados também acerca das classes de ordens e grafos que podem ser representados por dois tamanhos específicos, no que se refere à hierarquia de inclusão entre tais classes