×

Comparability digraphs: an analogue of comparability graphs. (English) Zbl 07790214

Summary: Comparability graphs are a popular class of graphs. We introduce as the digraph analogue of comparability graphs the class of comparability digraphs. We show that many concepts such as implication classes and the knotting graph for a comparability graph can be naturally extended to a comparability digraph. We give a characterization of comparability digraphs in terms of their knotting graphs. Semicomplete comparability digraphs contain in a sense all comparability graphs. One instrumental technique for analyzing the structure of comparability graphs is the Triangle Lemma for graphs (cf. [M. C. Golumbic, Computing 18, 199–208 (1977; Zbl 0365.05025)]). Using Triangle Lemma, Golumbic proved that a graph is a comparability graph if and only if no implication class of the graph is equal to its inverse. We give examples to show that a similar statement does not hold for general digraphs. We prove that it holds for semicomplete digraphs, that is, a semicomplete digraph is a comparability digraph if and only if no implication class of the digraph is equal to its inverse. The proof is done by generalizing the Triangle Lemma for graphs to semicomplete digraphs. This yields an \(\mathcal{O}( n^3)\)-time recognition algorithm for semicomplete comparability digraphs where \(n\) is the number of vertices of the input digraph. The correctness of the algorithm also implies several other characterizations for semicomplete comparability digraphs, akin to those for comparability graphs.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C75 Structural characterization of families of graphs

Citations:

Zbl 0365.05025
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anstee, R. P.; Farber, M., Characterizations of totally balanced matrices. J. Algorithms, 215-230 (1984) · Zbl 0551.05026
[2] Bechet, D.; de Groote, P.; Retoré, C., A complete axiomatisation of the inclusion of series-parallel partial orders, 230-240 · Zbl 1379.06001
[3] Boechner, D., Oriented threshold graphs. Australas. J. Comb., 43-53 (2018) · Zbl 1404.05065
[4] Deineko, V.; Rudolf, R.; Woeginger, G. J., A general approach to avoiding two by two submatrices. Computing, 371-388 (1994) · Zbl 0804.05014
[5] Gallai, T., Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung., 25-66 (1967) · Zbl 0153.26002
[6] Golumbic, M. C., The complexity of comparability graph recognition and coloring. Computing, 199-208 (1977) · Zbl 0365.05025
[7] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press · Zbl 0541.05054
[8] Haskins, L.; Rose, D. J., Toward characterization of perfect elimination digraphs. SIAM J. Comput., 217-224 (1973) · Zbl 0288.05115
[9] Hell, P.; Huang, J., Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs. J. Graph Theory, 361-374 (1995) · Zbl 0835.05064
[10] Hell, P.; Huang, J.; Lin, J. C.-H.; McConnell, R. M., Bipartite analogues of comparability and cocomparability graphs. SIAM J. Discrete Math., 1969-1983 (2020) · Zbl 1450.05089
[11] Hell, P.; Huang, J.; McConnell, R. M.; Rafiey, A., Min-orderable digraphs. SIAM J. Discrete Math., 1710-1724 (2020) · Zbl 1450.05036
[12] Hoffman, A. J.; Kolen, A. W.; Sakarovitch, M., Totally-balanced and greedy matrices. SIAM J. Algebraic Discrete Methods, 721-730 (1985) · Zbl 0573.05041
[13] Klinz, B.; Rudolf, R.; Woeginger, G. J., Permuting matrices to avoid forbidden submatrices. Discrete Appl. Math., 223-248 (1995) · Zbl 0837.05031
[14] Lamar, M. D., Split digraphs. Discrete Math., 1314-1325 (2012) · Zbl 1241.05116
[15] Lin, M. C.; Soulignac, F. J.; Szwarcfiter, J. L., Arboricity, h-index, and dynamic algorithms. Theor. Comput. Sci., 75-90 (2012) · Zbl 1243.68228
[16] Lubiw, A., Γ-free matrices (1982), University of Waterloo, Master’s thesis
[17] McConnell, R. M.; Spinrad, J. P., Modular decomposition and transitive orientation. Discrete Math., 189-241 (1999) · Zbl 0933.05146
[18] Sen, M.; Das, S.; Roy, A. B.; West, D. B., Interval digraphs: an analogue of interval graphs. J. Graph Theory, 189-202 (1989) · Zbl 0671.05039
[19] Sen, M.; Das, S.; West, D. B., Circular-arc digraphs: a characterization. J. Graph Theory, 581-592 (1989) · Zbl 0689.05025
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.