As árvores características dos grafos cordais comparabilidade não possuem grau limitado
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
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.
