Semi-strict chordality of digraphs. (English) Zbl 07850269
Summary: Chordal graphs are important in structural graph theory. Chordal digraphs are a digraph analogue of chordal graphs and have been a subject of active studies recently. Unlike chordal graphs, chordal digraphs lack many structural properties such as forbidden subdigraph or representation characterizations. In this paper we introduce the notion of semi-strict chordal digraphs which form a class strictly between chordal digraphs and chordal graphs. Semi-strict chordal digraphs have rich structural properties. We characterize semi-strict chordal digraphs in terms of knotting graphs, a notion analogous to the one introduced by Gallai for the study of comparability graphs. We also give forbidden subdigraph characterizations of semi-strict chordal digraphs within the classes of locally semicomplete digraphs and weakly quasi-transitive digraphs.
Keywords:
chordal graph; chordal digraph; strict chordal digraph; semi-strict chordal digraph; knotting graph; weakly quasi-transitive digraph; locally semicomplete digraph; forbidden subdigraph characterizationReferences:
| [1] | Bang-Jensen, J., Locally semicomplete digraphs: a generalization of tournaments, J. Graph Theory, 14, 371-390, 1990 · Zbl 0703.05026 · doi:10.1002/jgt.3190140310 |
| [2] | Bang-Jensen, J.; Huang, J., Quasi-transitive digraphs, J. Graph Theory, 20, 141-161, 1995 · Zbl 0832.05048 · doi:10.1002/jgt.3190200205 |
| [3] | Gallai, T., Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hung., 18, 25-66, 1967 · Zbl 0153.26002 · doi:10.1007/BF02020961 |
| [4] | Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory B, 16, 47-56, 1974 · Zbl 0266.05101 · doi:10.1016/0095-8956(74)90094-X |
| [5] | Golumbic, MC, Algorithmic Graph Theory and Perfect Graphs, 1980, New York: Academic Press, New York · Zbl 0541.05054 |
| [6] | Haskins, L.; Rose, DJ, Toward characterization of perfect elimination digraphs, SIAM J. Comput., 2, 217-224, 1973 · Zbl 0288.05115 · doi:10.1137/0202018 |
| [7] | Hell, P.; Hernández-Cruz, C., Strict chordal and strict split digraphs, Discrete Appl. Math., 216, 609-617, 2017 · Zbl 1358.05125 · doi:10.1016/j.dam.2016.02.009 |
| [8] | Huang, J.; Ye, YY, Chordality of locally semicomplete and weakly quasi-transitive digraphs, Discrete Math., 344, 112362, 2021 · Zbl 1462.05158 · doi:10.1016/j.disc.2021.112362 |
| [9] | Kleitman, DJ, A note on perfect elimination digraphs, SIAM J. Comput., 3, 280-282, 1974 · doi:10.1137/0203022 |
| [10] | McKee, TA, Strict chordal digraphs viewed as graphs with distinguished edges, Discrete Appl. Math., 247, 122-126, 2018 · Zbl 1394.05039 · doi:10.1016/j.dam.2018.03.061 |
| [11] | Meister, D.; Telle, JA, Chordal digraphs, Theoret. Comput. Sci., 463, 73-83, 2012 · Zbl 1256.05088 · doi:10.1016/j.tcs.2012.06.019 |
| [12] | Rose, DJ; Tarjan, RE; Lueker, GS, Algorithmic aspects of vertex elimination on graph, SIAM J. Comput., 5, 266-283, 1976 · Zbl 0353.65019 · doi:10.1137/0205021 |
| [13] | Ye, Y.Y.: On Chordal Digraphs and Semi-Strict Chordal Digraphs. Master thesis, University of Victoria, (2019) · Zbl 07724752 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
