As árvores características dos grafos cordais comparabilidade não possuem grau limitado

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

Resumo


Um grafo G é cordal comparabilidade se é simultaneamente cordal e de comparabilidade, ou seja, todo ciclo em G de tamanho pelo menos 4 possui uma corda e G admite uma orientação transitiva de suas arestas. Por ser cordal, todo grafo cordal comparabilidade possui uma árvore característica. Provamos a inexistência de um limite superior para o grau máximo de árvores características dos grafos cordais comparabilidade. Mais especificamente, provamos que para todo n ≥ 3, existe um grafo cordal comparabilidade RSn tal que sua árvore característica é única e isomorfa a K1,n. Este resultado apresenta um contraste entre os grafos cordais comparabilidade e os grafos de intervalo, outra importante subclasse de grafos cordais, que sempre possuem uma árvore característica cujo grau máximo é menor ou igual a 2.

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.

Branstädt, A., Le, V. B., and Spinrad, J. P. (2004). Graph Classes: a Survey. SIAM.

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

Golumbic, M. C. and Scheinerman, E. R. (1989). Containment graphs, posets, and related classes of graphs. Annals of the New York Academy of Sciences, 555:92–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:46–61.

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

Ohsugi, H. and Hibi, T. (2016). A Gröbner basis characterization for chordal comparability graphs. European Journal of Combinatorics, 1:75–78.

W. T. Trotter, J. (1992). Combinatorics and Partially Ordered Sets – Dimension Theory. Johns Hopkins University Press.
Publicado
06/08/2023
CERIOLI, Márcia R.; SOUTO, Rodrigo Fernandes; VIANA, Petrucio. As árvores características dos grafos cordais comparabilidade não possuem grau limitado. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 60-63. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.230521.