A Classe de Grafos PI

Seja F uma família de conjuntos. Podemos associar a F um grafo, G, da seguinte forma: cada conjunto de F corresponde a um vértice de G e existe uma aresta ligando dois vértices em G se, e somente se, os conjuntos correspondentes a esses vértices se intersectam. O grafo G é chamado Grafo Interse\c cão da família F. \par Considere duas retas paralelas $r_1$ e $r_2$. Seja F uma família de segmentos de reta com extremos em $r_1$ e $r_2$. O grafo interse\c cão dos elementos de F é chamado Grafo Permuta\c cão. A classe dos Grafos Permuta\c cão foi generalizada por Corneil e Kamula, permitindo que a família F contenha triângulos com um lado em $r_1$ e um vértice em $r_2$. O grafo interse\c cão de uma família de triângulos entre duas retas paralelas, é chamado Grafo PI. Outra generaliza\c cão, permite trapézios entre as duas retas paralelas. O grafo interse\c cão dessa família de trapézios é denominado Grafo Trapezóide. \par Uma conseqüência direta das defini\c cões é a rela\c cão de continência entre as classes: Permuta\c cão $\subset$ PI $\subset$ Trapezóide. São conhecidas caracteriza\c cões e algoritmos polinomiais para o reconhecimento tanto dos grafos Pemuta\c cão quanto dos grafos Trapezóide. Entretanto, esses problemas continuam abertos para os grafos PI. \par Considerando os grafos PI, identificamos uma subclasse obtida restringindo os triângulos da família F a triângulos não obtusângulos. Essa subclasse recebeu o nome de PI-Especial. Outra subclasse dos grafos PI é a classe dos Grafos de Intervalos, definida com o classe dos grafos interse\c cão de famílias de intervalos linearmente ordenados. Para essa classe, são conhecidas caracteriza\c cões e algoritmos de reconhecimento lineares. Provamos que PI-Especial e Intervalos são exatamente a mesma classe e que um grafo PI não é grafo de Intervalos se, e somente se, possui um $C_4$ como subgrafo induzido. \par Um grafo $G$ para o qual existe uma orienta\c cão transitiva das arestas é chamado Grafo de Comparabilidade. Um grafo cujo complemento $\overline{G}$ é grafo de Comparabilidade chama-se Grafo de Co-comparabilidade. Sabe-se que PI $\subset$ Co-comparabilidade. Os grafos de Comparabilidade foram caracterizados por Gallai através da família dos grafos proibidos para Comparabilidade, a Família de Gallai. Provamos que um grafo da Família de Gallai é grafo de Co-comparabilidade e não é PI se, e somente se, possui um $\overline{C_{2n}}$, $n > 2$, como subgrafo induzido.

2004