Article ID Journal Published Year Pages File Type
4651647 Electronic Notes in Discrete Mathematics 2015 6 Pages PDF
Abstract

The aim of the present work is the study of those posets that admit a containment model mapping vertices into paths of a tree, and their comparability graphs named CPT graphs. Answering a question posed by J.Spinrad, we prove that the dimension of CPT graphs is unbounded. We show that every tree is CPT. When ever transitive orientation of the edges of a comparability graph G defines a CPT poset, we say that G is strong-CPT. When both some transitive orientation of G and its reverse are CPT, we say that G is dually-CPT. Split comparability graphs that are dually-CPT or strong-CPT are characterized by forbidden induced subgraphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics