Chordal comparability graphs as intersection graphs

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

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

Abstract

A graph G is chordal if every cycle of size at least 4 in G has a chord; it is a comparability graph if it admits a transitive orientation of its edges; and it is a chordal comparability graph if it is both a chordal graph and a comparability graph. Chordal graphs are the graphs of intersection of subtrees of a tree. It is still an unanswered question whether there is an interesting class C such that the comparability graphs are the intersection graphs of C. In this work, we define a class of families of subtrees T such that the chordal comparability graphs are the intersection graphs of T.

References

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.