zbMATH — the first resource for mathematics

Cover-incomparability graphs and chordal graphs. (English) Zbl 1208.05105
Summary: The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova and A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26, No. 3, 229-236 (2009; Zbl 1172.05049)], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] Brandstädt, A.; Le, V.B.; Spinrad, J.P., Graphs classes: A survey, (1999), SIAM Philadelphia
[2] 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) · Zbl 1219.06004
[3] Changat, M.; Klavžar, S.; Mulder, H.M., The all-paths transit function of a graph, Czechoslovak math. J., 51, 126, 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] Heggernes, P.; Kratsch, D., Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nordic J. comput., 14, 87-108, (2007) · Zbl 1169.68653
[7] Hell, P.; Klein, S.; Nogueira, L.T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete appl. math., 141, 185-194, (2004) · Zbl 1043.05097
[8] Hopcroft, J.; Tarjan, R.E., Efficient algorithms for graph manipulation, Commun. ACM, 16, 372-378, (1973)
[9] Jamison-Waldner, R.E., Convexity and block graphs, Congr. numer., 33, 129-142, (1981) · Zbl 0495.05056
[10] Mathews, A.; Mathews, J., Transit functions on posets and lattices, (), 105-116 · Zbl 1160.06002
[11] Maxová, J.; Pavlíkova, P.; Turzík, A., On the complexity of cover-incomparability graphs of posets, Order, 26, 229-236, (2009) · Zbl 1172.05049
[12] Mo, Z.; Williams, K., Algorithms on block-complete graphs, Lecture notes in comput. sci., 507, 34-40, (1991)
[13] Morgana, M.A.; Mulder, H.M., The induced path convexity, betweenness and svelte graphs, Discrete math., 254, 349-370, (2002) · Zbl 1003.05090
[14] Mulder, H.M., The interval function of a graph, (1980), Mathematisch Centrum Amsterdam · Zbl 0446.05039
[15] Mulder, H.M., Transit functions on graphs and posets, (), 117-130 · Zbl 1166.05019
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.