The Library
Boundary properties of factorial classes of graphs
Tools
Lozin, Vadim V. and Zamaraev, Victor (2015) Boundary properties of factorial classes of graphs. Journal of Graph Theory, Volume 78 (Number 3). pp. 207-218. doi:10.1002/jgt.21799 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.21799
Abstract
For a class of graphs X, let inline image be the number of graphs with vertex set inline image in the class X, also known as the speed of X. It is known that in the family of hereditary classes (i.e. those that are closed under taking induced subgraphs) the speeds constitute discrete layers and the first four lower layers are constant, polynomial, exponential, and factorial. For each of these four layers a complete list of minimal classes is available, and this information allows to provide a global structural characterization for the first three of them. The minimal layer for which no such characterization is known is the factorial one. A possible approach to obtaining such a characterization could be through identifying all minimal superfactorial classes. However, no such class is known and possibly no such class exists. To overcome this difficulty, we employ the notion of boundary classes that has been recently introduced to study algorithmic graph problems and reveal the first few boundary classes for the factorial layer.
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: | March 2015 | ||||||
Dates: |
|
||||||
Volume: | Volume 78 | ||||||
Number: | Number 3 | ||||||
Page Range: | pp. 207-218 | ||||||
DOI: | 10.1002/jgt.21799 | ||||||
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 |