zbMATH — the first resource for mathematics

Which distance-hereditary graphs are cover-incomparability graphs? (English) Zbl 1286.05039
Summary: In this paper we deal with cover-incomparability graphs of posets, or briefly C-I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C-I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C-I graphs? It follows that C-I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C-I graphs in general is known to be NP-complete.

05C12 Distance in graphs
05C75 Structural characterization of families of graphs
06A06 Partial orders, general
Full Text: DOI
[1] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, Journal of Combinatorial Theory, Series B, 41, 2, 182-208, (1986) · Zbl 0605.05024
[2] A. Brandstädt, V.B. Le, J. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 1999, ISBN 0-89871-432-X.
[3] Brešar, B.; Changat, M.; Gologranc, T.; Mathews, J.; Mathews, A., Cover-incomparability graphs and chordal graphs, Discrete Applied Mathematics, 158, 335-347, (2010) · Zbl 1208.05105
[4] Brešar, B.; Changat, M.; Klavžar, S.; Kovše, M.; Mathews, J.; Mathews, A., Cover-incomparability graphs of posets, Order, 25, 335-347, (2008) · Zbl 1219.06004
[5] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canadian Journal of Mathematics, 16, 539-548, (1964) · Zbl 0121.26003
[6] Howorka, E., A characterization of distance-hereditary graphs, The Quarterly Journal of Mathematics, Oxford, Second Series, 28, 112, 417-420, (1977) · Zbl 0376.05040
[7] Lekkerkerker, C. B.; Boland, J. C., Representation of finite graphs by a set of intervals on the real line, Fundamenta Mathematicae, 51, 45-64, (1962) · Zbl 0105.17501
[8] Maxová, J.; Pavlíková, P.; Turzík, D., On the complexity of cover-incomparability graphs of posets, Order, 26, 229-236, (2009) · Zbl 1172.05049
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.