Recent results on containment graphs of paths in a tree

Abstract

In this paper, motivated by the questions posed by Spinrad in Spinrad (2003) and Golumbic and Trenk (2004), we investigate those posets that admit a containment model mapping vertices into paths of a tree and their comparability graphs, named CPT posets and CPT graphs, respectively. We present a necessary condition to be CPT and prove it is not sufficient. We provide further examples of CPT posets P whose dual Pd is non CPT. Thus, we introduce the notion of dually-CPT and strong-CPT posets. We demonstrate that, unlike what happens with posets admitting a containment model using interval of the line, the dimension and the interval dimension of CPT posets is unbounded. On the other hand, we find that the dimension of a CPT poset is at most the number of leaves of the tree used in the containment model. We give a characterization of CPT (also dually-CPT and strong-CPT) split posets by a family of forbidden subposets. We prove that every tree is strong-CPT.