×

zbMATH — the first resource for mathematics

Cover-incomparability graphs of posets. (English) Zbl 1219.06004
Summary: Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems are also stated.

MSC:
06A07 Combinatorics of partially ordered sets
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, J. Comb. Theory, Ser. B, 41, 182-208, (1986) · Zbl 0605.05024
[2] Brandstädt, A., Le, V.B., Spinrad, J.: Graph Classes. SIAM, Philadelphia (1999) · Zbl 0919.05001
[3] Changat, M.; Klavžar, S.; Mulder, H. M., The all-paths transit function of a graph, Czech. Math. J., 51, 439-448, (2001) · Zbl 0977.05135
[4] Changat, M.; Mathews, J., Induced path transit function, monotone and Peano axioms, Discrete Math., 286, 185-194, (2004) · Zbl 1056.05044
[5] Changat, M.; Mulder, H. M.; Sierksma, G., Convexities related to path properties on graphs, Discrete Math., 290, 117-131, (2005) · Zbl 1058.05043
[6] Grätzer, G.: General Lattice Theory, 2nd edn. Birkhauser, Basel (1998) · Zbl 0909.06002
[7] Howorka, E., A characterization of distance-hereditary graphs, Q. J. Math. Oxford Ser. 2, 28, 417-420, (1977) · Zbl 0376.05040
[8] Larrión, F.; Pizaña, M. A.; Villarroel-Flores, R., Posets, clique graphs and their homotopy type, Eur. J. Comb., 29, 334-342, (2008) · Zbl 1127.05073
[9] Mathews, A.; Mathews, J.; Changat, M. (ed.); Klavžar, S. (ed.); Mulder, H. M. (ed.); Vijayakumar, A. (ed.), Transit functions on posets and lattices, 105-116, (2008), Mysore
[10] Morgana, M. A.; Mulder, H. M., The induced path convexity, betweenness and svelte graphs, Discrete Math., 254, 349-370, (2002) · Zbl 1003.05090
[11] Mulder, H.M.: The Interval Function of a Graph. Mathematisch Centrum, Amsterdam (1980) · Zbl 0446.05039
[12] Mulder, H. M.; Changat, M. (ed.); Klavžar, S. (ed.); Mulder, H. M. (ed.); Vijayakumar, A. (ed.), Transit functions on graphs (and posets), 117-130, (2008), Mysore
[13] Nešetřil, J.; Rödl, V., Complexity of diagrams, Order, 3, 321-330, (1987) · Zbl 0808.06004
[14] Nešetřil, J.; Rödl, V., More on the complexity of cover graphs, Comment. Math. Univ. Carol., 36, 269-278, (1995) · Zbl 0829.06002
[15] Rival, I., The role of graphs in the theory of ordered sets and its applications, J. Symb. Log., 57, 269-271, (1992)
[16] Trotter, W. T., Graphs and partially ordered sets: recent results and new directions, Congr. Numer., 116, 253-278, (1996) · Zbl 0902.05038
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.