End vertices in containment interval graphs

Abstract

An interval containment model of a graph maps vertices intointervals of a line in such a way that two vertices are adjacent ifand only if the corresponding intervals are comparable under theinclusion relation. Graphs admitting an interval containment modelare called containment interval graphs or CI graphs for short. Avertex v of a CI graph G is an end-vertex if there is an intervalcontainment model of G in which the left endpoint of the intervalcorresponding to v is less than all other endpoints. In this work,we present a characterization of end-vertices in terms of forbiddeninduced subgraphs.