Hell, Pavol; Hernández-Cruz, César Strict chordal and strict split digraphs. (English) Zbl 1358.05125 Discrete Appl. Math. 216, Part 3, 609-617 (2017). Summary: We introduce new versions of chordal and split digraphs, and explore their similarity with the corresponding undirected notions. Cited in 1 ReviewCited in 2 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C85 Graph algorithms (graph-theoretic aspects) Keywords:split digraph; chordal digraph; perfect digraph; recognition algorithm PDFBibTeX XMLCite \textit{P. Hell} and \textit{C. Hernández-Cruz}, Discrete Appl. Math. 216, Part 3, 609--617 (2017; Zbl 1358.05125) Full Text: DOI References: [1] Andres, S. D.; Hochstättler, W., Perfect digraphs, J. Graph Theory, 79, 21-29 (2015) · Zbl 1312.05059 [2] Bender, E. A.; Richmond, L. B.; Wormald, N. C., Almost all chordal graphs split, J. Aust. Math. Soc. A, 38, 214-221 (1985) · Zbl 0571.05026 [3] Benzer, S., On the topology of the genetic fine structure, Proc. Natl. Acad. Sci. USA, 45 (1959), 16-7-1620 [4] Berge, C., Perfect graphs, (Six Papers on Graph Theory (1963), Indian Statistical Institute: Indian Statistical Institute Calcutta), 1-21 [5] Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034 [6] Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, P.; Vušković, K., Recognizing Berge graphs, Combinatorica, 25, 143-186 (2005) · Zbl 1089.05027 [7] Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. of Math., 164, 51-229 (2006) · Zbl 1112.05042 [8] Cohen, J. E., Food Webs and Niche Space (1978), Princeton University Press: Princeton University Press Princeton [9] Corneil, D. G.; Olariu, S.; Stewart, L., The LBFS structure and recognition of interval graphs, SIAM J. Discrete Math., 23, 1905-1953 (2009) · Zbl 1207.05131 [10] Damaschke, P., Forbidden ordered subgraphs, Topics in Combinatorics and Graph Theory, 219-229 (1990) · Zbl 0736.05065 [11] Das, S.; Sen, M.; Roy, A. B.; West, D., Interval digraphs: an analogue of interval graphs, J. Graph Theory, 13, 189-202 (1989) · Zbl 0671.05039 [12] Feder, T.; Hell, P.; Huang, J.; Rafiey, A., Interval graphs, adjusted interval graphs and reflexive list homomorphisms, Discrete Appl. Math., 160, 697-707 (2012) · Zbl 1236.05092 [13] Foldes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315 (1977) [14] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 835-855 (1965) · Zbl 0132.21001 [15] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B, 16, 47-56 (1974) · Zbl 0266.05101 [16] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003 [17] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 [18] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056 [19] Habib, M.; McConnell, R.; Paul, Ch.; Viennot, L., Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing, Theoret. Comput. Sci., 234, 59-84 (2000) · Zbl 0945.68189 [20] Harary, F.; Kabell, J. A.; McMorris, F. R., Interval acyclic digraphs, Ars Combinatoria 29A, 59-64 (1990) · Zbl 0711.05024 [21] Harary, F.; Kabell, J. A.; McMorris, F. R., Subtree acyclic digraphs, Ars Combin., 34, 93-95 (1992) · Zbl 0770.05084 [22] Haskins, L.; Rose, D. J., Toward characterization of perfect elimination digraphs, SIAM J. Comput., 2, 217-224 (1973) · Zbl 0288.05115 [23] Heggernes, P.; Kratsch, D., Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nordic J. Comput., 14, 87-108 (2007) · Zbl 1169.68653 [24] Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097 [25] Korte, N.; Möhring, R. H., An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Comput., 18, 68-81 (1989) · Zbl 0678.68043 [26] Kratsch, D.; McConnell, R. M.; Mehlhorn, K.; Spinrad, J. P., Certifying algorithms for recognizing interval graphs and permutation graphs, SODA, 14, 158-167 (2003) · Zbl 1094.68615 [27] LaMar, D., Split digraphs, Discrete Math., 312, 1314-1325 (2012) · Zbl 1241.05116 [28] Lekkerkerker, C. G.; Boland, J. C., Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45-64 (1962) · Zbl 0105.17501 [29] McMorris, F. R.; Mulder, H. M., Subpath acyclic digraphs, Discrete Math., 154, 189-201 (1996) · Zbl 0851.05054 [30] Meister, D.; Telle, J. A., Chordal digraphs, Theoret. Comput. Sci., 463, 73-83 (2012) · Zbl 1256.05088 [31] Müller, H., Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Appl. Math., 78, 189-205 (1997) · Zbl 0890.68103 [32] Neumann-Lara, V., Seminúcleos de una digráfica, An. Inst. Mat. Univ. Nac. Autónoma México, 11, 55-62 (1971) [34] Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination in graphs, SIAM J. Comput., 5, 266-283 (1976) · Zbl 0353.65019 [35] Tarjan, Robert E.; Yannakakis, Mihalis, Addendum: simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 14, 254-255 (1985) · Zbl 0562.68055 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.