Cohen-Macaulay permutation graphs
DOI:
https://doi.org/10.7146/math.scand.a-149033Abstract
In this article, we characterize Cohen-Macaulay permutation graphs. In particular, we show that a permutation graph is Cohen-Macaulay if and only if it is well-covered and there exists a unique way of partitioning its vertex set into $r$ disjoint maximal cliques, where $r$ is the cardinality of a maximal independent set of the graph. We also provide some sufficient conditions for a comparability graph to be a uniquely partially orderable (UPO) graph.
References
Beineke, L. W., and Bagga, J. S., Line graphs and line digraphs, Developments in Mathematics, vol. 68, Springer, Cham, 2021. https://doi.org/10.1007/978-3-030-81386-4
Crupi, M., Rinaldo, G., and Terai, N., Cohen-Macaulay edge ideal whose height is half of the number of vertices, Nagoya Math. J. 201 (2011), 117–131. https://doi.org/10.1215/00277630-2010-018
Dushnik, B., and Miller, E. W., Partially ordered sets, Amer. J. Math. 63 (1941), 600–610. https://doi.org/10.2307/2371374
Even, S., Pnueli, A., and Lempel, A., Permutation graphs and transitive graphs, J. Assoc. Comput. Mach. 19 (1972), 400–410. https://doi.org/10.1145/321707.321710
Faridi, S., Monomial ideals via square-free monomial ideals, Commutative algebra, 85–114, Lect. Notes Pure Appl. Math., 244, Chapman & Hall/CRC, Boca Raton, FL, 2006. https://doi.org/10.1201/9781420028324.ch8
Gallai, T., Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66. https://doi.org/10.1007/BF02020961
Golumbic, M. C., Rotem, D., and Urrutia, J., Comparability graphs and intersection graphs, Discrete Math. 43 (1983), no. 1, 37–46. https://doi.org/10.1016/0012-365X(83)90019-5
Herzog, J., and Hibi, T., Distributive lattices, bipartite graphs and Alexander duality, J. Algebraic Combin. 22 (2005), no. 3, 289–302. https://doi.org/10.1007/s10801-005-4528-1
Herzog, J., Hibi, T., and Zheng, X., Cohen-Macaulay chordal graphs, J. Combin. Theory Ser. A 113 (2006), no. 5, 911–916. https://doi.org/10.1016/j.jcta.2005.08.007
Jahangir, R., and Veer, D., On Cohen-Macaulay posets of dimension 2 and permutation graphs, Submitted. arXiv:2305.04535.
Maffray, F., and Preissmann, M., A translation of Gallai's paper: “Transitiv orientierbare Graphen”, Perfect graphs, 25–66, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, Chichester, 2001.
Möhring, R. H., Almost all comparability graphs are UPO, Discrete Math. 50 (1984), no. 1, 63–70. https://doi.org/10.1016/0012-365X(84)90035-9
Morey, S., Reyes, E., and Villarreal, R. H., Cohen-Macaulay, shellable and unmixed clutters with a perfect matching of König type, J. Pure Appl. Algebra 212 (2008), no. 7, 1770–1786. https://doi.org/10.1016/j.jpaa.2007.11.010
Pnueli, A., Lempel, A., and Even, S., Transitive orientation of graphs and identification of permutation graphs, Canadian J. Math. 23 (1971), 160–175. https://doi.org/10.4153/CJM-1971-016-5
The Sage Developers, Sagemath, the Sage Mathematics Software System (Version 9.2), 2020, tt https://www.sagemath.org.
Trotter, W. T., Jr., Moore, J. I., Jr., and Sumner, D. P., The dimension of a comparability graph, Proc. Amer. Math. Soc. 60 (1976), 35–38 (1977). https://doi.org/10.2307/2041106
Villarreal, R. H., Cohen-Macaulay graphs, Manuscripta Math. 66 (1990), no. 3, 277–293. https://doi.org/10.1007/BF02568497
