The Application of Novel Technology in Cultural Heritage Graph Theory, Combinatorics and Algorithms The Application of Novel Technology in Cultural Heritage Graph Theory, Combinatorics and Algorithms ???? The Application of Novel Technology in Cultural Heritage Graph Theory, Combinatorics and Algorithms

 

Containment Graphs of Paths in a Tree

 

Liliana Alcon

 

Abstract

 

A containment model of a poset (X, <) maps each element x of X into a set Mx in such a way that x < y  if and only if Mx is a proper subset of My. It is well known that posets admitting a containment model mapping vertices into intervals of the line (CI posets for short) are the posets with dimension at most 2; thus, if a transitive orientation of a comparability graph G is a CI poset then any other transitive orientation of G is also a CI poset. Comparability graphs of CI posets were shown to be the permutation graphs.

Generalizing this ideas, M. Golumbic, first in a work with E. Scheinerman and then in the book with A. Trenk, suggested the study of posets admitting a containment model mapping vertices into paths of a tree and their comparability graphs, called CPT posets and CPT graphs, respectively.

In this talk, based on a joint work with N. Gudiño and M. Gutierrez, I will present our first results on this line. Answering a question posed by J. Spinrad, we proved that, unlike what happens with CI posets, the dimension and the interval dimension of CPT posets is unbounded. On the other hand, we will see that the dimension of a CPT poset is at most the number of leaves of the tree used in the containment model. An example of a CPT poset P whose dual Pd is non CPT motivated us to introduce the notion of dually-CPT and strong-CPT. I will show that trees are strong-CPT and will give a characterization of CPT (also dually-CPT and strong-CPT) split posets by a finite family of forbidden subposets. Also we will consider the problem of characterizing CPT posets restricted to posets whose comparability graphs are k-trees. Several open problems will be posed.