The Library
Vertex ordering characterizations of graphs of bounded asteroidal number
Tools
Corneil, Derek G. and Stacho, Juraj (2014) Vertex ordering characterizations of graphs of bounded asteroidal number. Journal of Graph Theory, Volume 78 (Number 1). pp. 61-79. doi:10.1002/jgt.21795 ISSN 0364-9024.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1002/jgt.21795
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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | Journal of Graph Theory | ||||||||
Publisher: | John Wiley & Sons Ltd. | ||||||||
ISSN: | 0364-9024 | ||||||||
Official Date: | 10 November 2014 | ||||||||
Dates: |
|
||||||||
Volume: | Volume 78 | ||||||||
Number: | Number 1 | ||||||||
Page Range: | pp. 61-79 | ||||||||
DOI: | 10.1002/jgt.21795 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |