Os grafos cordais comparabilidade como grafos de interseção

• Márcia R. Cerioli UFRJ
• Rodrigo Fernandes Souto UFRJ
• Petrucio Viana UFF

DOI: https://doi.org/10.5753/etc.2024.2950

Resumo

Um grafo G é cordal se todo ciclo de tamanho pelo menos 4 em G possui uma corda; é de comparabilidade se admite uma orientação transitiva de suas arestas; e é cordal comparabilidade se é simultaneamente cordal e de comparabilidade. Os grafos cordais são os grafos de interseção de subárvores de uma árvore. é uma questão ainda sem resposta se existe uma classe interessante C tal que os grafos de comparabilidade são os grafos de interseção de C. Neste trabalho, definimos uma classe de famílias de subárvores T tal que os grafos cordais comparabilidade são os grafos de interseção de T.

Referências

Borie, R. B. and Spinrad, J. P. (1999). Construction of a simple elimination scheme for a chordal comparability graph in linear time. Discrete Applied Mathematics, 91:287–292.

Cerioli, M. R., Souto, R. F., and Viana, P. (2023). As árvores características dos grafos cordais comparabilidade não possuem grau limitado. In Anais do VIII Encontro de Teoria da Computação, pages 60–63. SBC.

Golumbic, M. C. (2004). Algorithmic Graph Theory and Perfect Graphs. Elsevier, 2th edition.

Golumbic, M. C. and Scheinerman, E. R. (1999). Containment graphs, posets, and related classes of graphs. Annals of the New York Academy of Sciences, 555:192–204.

Kierstead, H. A., Trotter, W. T., and Qin, J. (1992). The dimension of cycle-free orders. Order, 9:103–110.

Ma, T.-H. and Spinrad, J. P. (1991). Cycle-free partial orders and chordal comparability graphs. Order, 8:49–61.

McKee, T. A. and McMorris, F. R. (1999). Topics in Intersection Graph Theory. SIAM.

Ohsugi, H. and Hibi, T. (2017). A Gröbner basis characterization for chordal comparability graphs. European Journal of Combinatorics, 59:122–128.

Scheinerman, E. R. (1985). Characterizing intersection classes of graphs. Discrete Mathematics, 55:185–193.