Abstract
Cover-Incomparability graphs (C-I graphs) are graphs whose edge-set is the union of edge-sets of incomparability graph and the cover graph of some poset. We give a new characterization of Ptolemaic C-I graphs and prove that each C-I graph contains a Ptolemaic C-I graph as a spanning subgraph. This result is used to present several necessary conditions for a graph G being planar C-I graph. We present a hierarchy of subfamilies of chordal graphs in the class of C-I graphs and prove that many different graph families coincide in the class of C-I graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability Statement
Data sharing not applicable to this article as no data sets were generated or analysed during the current study, certified that this article is theoretical and contains no data sets that were generated or analysed during the current study.
References
Blair, J.R.S., Ravi, S.S.: TR-matching for chordal graphs. In: Proceedings Twenty-Seventh Conference on Communication, Control, and Computing, pp 72.81 (1989)
Bok, J., Maxová, J.: Characterizing subclasses of Cover-Incomparability graphs by forbidden subposets. Order 36, 349–358 (2019). https://doi.org/10.1007/s11083-018-9470-7
Brešar, B., Changat, M., Klavžar, S., Kovše, M., Mathew, J., Mathews, A.: Cover-incomparability graphs of posets. Order 25, 335–347 (2008)
Brešar, B., Changat, M., Gologranc, T., Mathew, J., Mathews, A.: Cover-incomparability graphs and chordal graphs. Discrete Appl. Math. 158, 1752–1759 (2010)
Brešar, B., Gologranc, T., Changat, M., Sukumaran, B.: Cographs which are Cover-Incomparability graphs of posets. Order 32, 179–187 (2015)
Brightwell, G., West, D. B.: Partially Ordered Sets, Chapter 11. In: Rosen, K.H (ed.) Handbook of Discrete and Combinatorial Mathematics, pp 717–752. CRC Press, Boca Raton (2000)
Golumbic, M.C., Peled, U.N.: Block duplicate graphs and a hierarchy of chordal graphs. Discrete Appl. Math. 124, 67–71 (2002)
Howorka, E.: A characterization of ptolemaic graphs. J. Graph Theory 5, 323–331 (1981)
Kennedy, W.: Strictly Chordal Graphs and Phylogenetic Roots. Master Thesis, University of Alberta (2005)
Kennedy, W., Lin, G., Yan, G.: Strictly chordal graphs are leaf powers. J. Discrete Algorithms 4, 511–525 (2006)
Markenzon, L., Pereira, P.R.C.: One phase algorithm for the determination of minimal vertex separators of chordal graphs. Int. Trans. Oper. Res. 17(6), 683–690 (2010)
Markenzon, L., Waga, C.F.E.M.: New results on ptolemaic graphs. Discrete Appl. Math. 196, 135–140 (2015)
Maxová, J., Turzík, D.: Which distance-hereditary graphs are cover-incomparability graphs?. Discrete Appl. Math. 161, 2095–2100 (2013)
Maxová, J., Dubcová, M., Pavlíková, P., Turzík, D.: Which k-trees are cover-incomparability graphs?. Discrete Appl. Math. 167, 222–227 (2014)
Maxová, J., Pavlíková, P., Turzík, D.: On the Complexity of cover-incomparability graphs of posets. Order 26(3), 229–236 (2009)
Acknowledgments
A.A. acknowledges the financial support from UGC Govt. of India for providing Junior Research Fellowship. M.C. acknowledges the financial support from SERB, Department of Science & Technology, Govt. of India (research project under MATRICS scheme No. MTR/2017/000238). The financial support from the Slovenian Research Agency (research core funding P1-0297, and projects J1-9109, J1-1693) is acknowledged by T.G.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Anil, A., Changat, M., Gologranc, T. et al. Ptolemaic and Planar Cover-incomparability Graphs. Order 38, 421–439 (2021). https://doi.org/10.1007/s11083-021-09549-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-021-09549-4