A Classe de Grafos PI

Autores

  • S. Almeida
  • C.P. de Mello
  • A. Gomide

DOI:

https://doi.org/10.5540/tema.2005.06.01.0033

Resumo

Neste trabalho mostramos que a representação de um grafo PI, grafo interseção de triângulos entre duas retas paralelas, que não é grafo de intervalo, contém um triângulo obtusângulo. Além disso, classificamos os grafos da família de Gallai que são PI.

Referências

[1] J.A. Bondy, U.S.R. Murty, “Graph Theory with Applications”, American Elsevier, New York, 1979.

K.S. Booth, G.S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comp. and Syst. Sci., 13 (1976), 335-379.

A. Brandst¨adt, V. Le, J. Spinrad, “Graph Classes - a Survey”, SIAM, Monographs on Discrete Math. and Applications, 1999.

F. Cheah, D.G. Corneil, On the structure of trapezoid graphs, Discrete Applied Math., 66 (1996), 109-133.

D.J. Corneil, P.A. Kamula, Extensions of permutation and interval graphs, Congressus Numerantium, 58 (1987), 267-275.

T. Gallai, Transitiv Orientierbare Graphen, Acta Math. Acad. Sci. Hung, 18 (1967), 25-66.

M.C. Golumbic, “Algorithmic Graph Theory and Perfect Graphs”, Academic Press, New York, 1980.

Downloads

Publicado

2005-06-01

Como Citar

Almeida, S., de Mello, C., & Gomide, A. (2005). A Classe de Grafos PI. Trends in Computational and Applied Mathematics, 6(1), 33–42. https://doi.org/10.5540/tema.2005.06.01.0033

Edição

v. 6 n. 1 (2005)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.