LINEAR ORDERINGS OF SUBFAMILIES OF AT-FREE GRAPHS

摘要

Asteroidal triple free (AT-free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT-free graphs. While for interval graphs it is obvious that there is always a linear ordering of the vertices, such that for each triple of independent vertices the middle one intercepts any path between the remaining vertices of the triple, it is not clear that such an ordering exists for AT-free graphs in general. In this paper we study graphs that are defined by enforcing such an ordering. In particular, we introduce two subfamilies of AT-free graphs, namely, path orderable graphs and strong asteroid free graphs. Path orderable graphs are defined by a linear ordering of the vertices that is a natural generalization of the ordering that characterizes cocomparability graphs. On the other hand, motivation for the definition of strong asteroid free graphs comes from the fundamental work of Gallai on comparability graphs. We show that cocomparability graphs is contained in path orderable graphs is contained in strong asteroid free graphs is contained in AT-free graphs. In addition, we settle the recognition question for the two new classes by proving that recognizing path orderable graphs is NP-complete, whereas the recognition problem for strong asteroid free graphs can be solved in polynomial time.