Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
Derek Gordon Corneil, Juraj Stacho · Journal of Graph Theory · 2014
Asteroidal Triple-free (AT-free) graphs have received considerable attention due to their inclusion of various important graphs families, such as interval and cocomparability graphs. The asteroidal number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component. (AT-free graphs have asteroidal number at most 2.) In this article, we characterize graphs of bounded asteroidal number by means of a vertex elimination ordering, thereby solving a long-standing open question in algorithmic graph theory. Similar characterizations are known for chordal, interval, and cocomparability graphs.