Caracterizações, reconhecimento e conjuntos independentes máximos de grafos de intervalo

Abstract

A 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.