A Classe de Grafos PI

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

Abstract


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.

References


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




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

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia