zbMATH — the first resource for mathematics

Which \(k\)-trees are cover-incomparability graphs? (English) Zbl 1284.05063
Summary: In this paper we deal with cover-incomparability graphs of posets. It is known that the class of cover-incomparability graphs is not closed on induced subgraphs which makes the study of structural properties of these graphs difficult. In this paper we introduce the notion of \(s\)-subgraph which enables us to define forbidden \(s\)-subgraphs (i.e. graphs that cannot appear as \(s\)-subgraphs of any cover-incomparability graph). We show that the family of minimal forbidden \(s\)-subgraphs is infinite even for cover-incomparability unit-interval graphs. Using the notion of \(s\)-subgraph we also answer the question which \(k\)-trees are cover-incomparability graphs and which chordal graphs without \(K_4\) are cover-incomparability graphs.

05C05 Trees
06A06 Partial orders, general
Full Text: DOI
[1] Brešar, B.; Changat, M.; Gologranc, T.; Mathews, J.; Mathews, A., Cover-incomparability graphs and chordal graphs, Discrete Appl. Math., 158, 1752-1759, (2010) · Zbl 1208.05105
[2] 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
[3] Diestel, R., (Graph Theory, Graduate Texts in Mathematics, (2005), Springer-Verlag) · Zbl 1074.05001
[4] Jamison-Waldner, R. E., Convexity and block graphs, Congr. Numer., 33, 129-142, (1981) · Zbl 0495.05056
[5] 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
[6] Maxová, J.; Turzík, D., Which distance-hereditary graphs are cover-incomparability graphs?, Discrete Appl. Math., 161, 13-14, 2095-2100, (2013) · Zbl 1286.05039
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.