Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number |
| |
Authors: | Derek G Corneil Juraj Stacho |
| |
Institution: | 1. DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF TORONTO, TORONTO, ONTARIO, CANADA;2. DIMAP AND MATHEMATICS INSTITUTE, UNIVERSITY OF WARWICK, COVENTRY, UNITED KINGDOM |
| |
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. |
| |
Keywords: | asteroidal triple AT‐free vertex elimination asteroidal number 05C15 05C75 |
|
|