We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number.
- Authors
Corneil, Derek G.; Stacho, Juraj
- Abstract
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.
- Subjects
VERTEX operator algebras; OPERATOR algebras; NUMBER theory; ALGEBRAIC number theory; GRAPH theory
- Publication
Journal of Graph Theory, 2015, Vol 78, Issue 1, p61
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.21795