Huang, Jing; Ye, Ying Ying Chordality of locally semicomplete and weakly quasi-transitive digraphs. (English) Zbl 1462.05158 Discrete Math. 344, No. 6, Article ID 112362, 9 p. (2021). Summary: Chordal graphs are important in the structural and algorithmic graph theory. A digraph analogue of chordal graphs was introduced by L. Haskins and D. J. Rose [SIAM J. Comput. 2, 217–224 (1973; Zbl 0288.05115)] but has not been the subject of active studies until recently when a characterization of semicomplete chordal digraphs in terms of forbidden subdigraphs was found by D. Meister and J. A. Telle [Theor. Comput. Sci. 463, 73–83 (2012; Zbl 1256.05088)].Locally semicomplete digraphs, quasi-transitive digraphs, and extended semicomplete digraphs are amongst the most popular generalizations of semicomplete digraphs. We extend the forbidden subdigraph characterization of semicomplete chordal digraphs to locally semicomplete chordal digraphs. We introduce a new class of digraphs, called weakly quasi-transitive digraphs, which contains quasi-transitive digraphs, symmetric digraphs, and extended semicomplete digraphs, but is incomparable to the class of locally semicomplete digraphs. We show that weakly quasi-transitive digraphs can be recursively constructed by simple substitutions from transitive oriented graphs, semicomplete digraphs, and symmetric digraphs. This recursive construction of weakly quasi-transitive digraphs, similar to the one for quasi-transitive digraphs, demonstrates the naturalness of the new digraph class. As a by-product, we prove that the forbidden subdigraphs for semicomplete chordal digraphs are the same for weakly quasi-transitive chordal digraphs. The forbidden subdigraph characterization of weakly quasi-transitive chordal digraphs generalizes not only the recent results on quasi-transitive chordal digraphs and extended semicomplete chordal digraphs but also the classical results on chordal graphs. Cited in 1 Document MSC: 05C20 Directed graphs (digraphs), tournaments 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) Keywords:chordal digraph; locally semicomplete digraph; weakly quasi-transitive digraph; forbidden subdigraph characterization Citations:Zbl 0288.05115; Zbl 1256.05088 PDFBibTeX XMLCite \textit{J. Huang} and \textit{Y. Y. Ye}, Discrete Math. 344, No. 6, Article ID 112362, 9 p. (2021; Zbl 1462.05158) Full Text: DOI arXiv References: [1] Bang-Jensen, J., Locally semicomplete digraphs: A generalization of tournaments, J. Graph Theory, 14, 371-390 (1990) · Zbl 0703.05026 [2] Bang-Jensen, J.; Guo, Y.; Gutin, G.; Volkmann, L., A classification of locally semicomplete digraphs, Discrete Math., 167-168, 101-114 (1997) · Zbl 0873.05072 [3] Bang-Jensen, J.; Gutin, G., (Classes of Directed Graphs. Classes of Directed Graphs, Springer Monographs in Mathematics (2018)) · Zbl 1398.05002 [4] Bang-Jensen, J.; Huang, J., Quasi-transitive digraphs, J. Graph Theory, 20, 141-161 (1995) · Zbl 0832.05048 [5] Bang-Jensen, J.; Huang, J., Kings in quasi-transitive digraphs, Discrete Math., 185, 19-27 (1998) · Zbl 0955.05048 [6] Bang-Jensen, J.; Huang, J.; Yeo, A., Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs, SIAM J. Discrete Math., 16, 335-343 (2003) · Zbl 1029.05063 [7] Galeana-Sánchez, H.; Rojas-Monroy, R., Kernels in quasi-transitive digraphs, Discrete Math., 306, 1969-1974 (2006) · Zbl 1100.05042 [8] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 [9] Haskins, L.; Rose, D. J., Toward characterization of perfect elimination digraphs, SIAM J. Comput., 2, 217-224 (1973) · Zbl 0288.05115 [10] Huang, J., On the structure of local tournaments, J. Combin. Theory Ser. B, 200-221 (1995) · Zbl 0820.05029 [11] Meister, D.; Telle, J. A., Chordal digraphs, Theoret. Comput. Sci., 463, 73-83 (2012) · Zbl 1256.05088 [12] Ye, Y. Y., On Chordal Digraphs and Semi-Strict Chordal Digraphs (2019), University of Victoria, (M.Sc. Thesis) 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.