Seminário de Teoria da Computação Relação entre Grafos PI, Família de Gallai e Grafos de Intervalo Sheila Morais de Almeida Sexta-feira, 8 de outubro de 2004 Auditório do IC (IC1), 13:00hs Resumo: Ao grafo interseção de triângulos entre duas retas paralelas chama-se grafo PI. Mostramos que a representação de um grafo PI que não é grafo de intervalo contém um triângulo obtusângulo e apresentamos uma relação entre a existência do triângulo obtusângulo na representação de um grafo G e a existência de um C*4* como subgrafo induzido de G. Além disso, classificamos os grafos da família de Gallai (grafos proibidos para comparabilidade) que são PI.