Premium
Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
Author(s) -
Corneil Derek G.,
Stacho Juraj
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21795
Subject(s) - combinatorics , mathematics , chordal graph , vertex (graph theory) , bounded function , independent set , indifference graph , discrete mathematics , maximal independent set , graph , 1 planar graph , mathematical analysis
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.