2025-06-062025-06-062024-12-09SOUZA, Ana Carolyne Pereira de. Caracterizações, reconhecimento e conjuntos independentes máximos de grafos de intervalo. 2024. 44 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Instituto de Informática, Universidade Federal de Goiás, Goiânia, 2024.http://repositorio.bc.ufg.br//handle/ri/27712A graph G is an interval graph if its vertex set can be represented by an interval intersection model on the real line. This monograph presents a study of some properties of interval graphs, such as the absence of induced cycles with four or more vertices and asteroidal triples. Based on the presented properties, given an interval graph G, we develop a polynomial-time algorithm that uses the perfect elimination scheme, obtained through the lexicographic breadth-first search algorithm, to create an interval model for the interval graph G. Additionally, we present a polynomial-time algorithm for determining a maximum independent set in an interval graph G. We also provide a characterization of unit interval graphs as interval graphs free of K1,3.porAcesso Abertohttp://creativecommons.org/licenses/by-nc-nd/4.0/Teoria dos grafosGrafos de intervaloModelo de interseçãoAlgoritmoConjunto independenteGraph theoryInterval graphsIntersection modelAlgorithmIndependent setTrabalho de conclusão de curso de graduação (TCCG)