The Library
Clique-width and the speed of hereditary properties
Tools
Allen, Peter, Lozin, Vadim V. and Rao, Michael (2009) Clique-width and the speed of hereditary properties. Electronic Journal of Combinatorics, Vol.16 (No.1). Article no. R35. ISSN 1077-8926.
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://www.combinatorics.org/Volume_16/v16i1toc.ht...
Abstract
In this paper, we study the relationship between the number of n-vertex graphs in a hereditary class X, also known as the speed of the class X, and boundedness of the clique-width in this class. We show that if the speed of X is faster than n!c(n) for any c, then the clique-width of graphs in X is unbounded, while if the speed does not exceed the Bell number B-n, then the clique-width is bounded by a constant. The situation in the range between these two extremes is more complicated. This area contains both classes of bounded and unbounded clique-width. Moreover, we show that classes of graphs of unbounded clique-width may have slower speed than classes where the clique-width is bounded.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Electronic Journal of Combinatorics | ||||
Publisher: | Electronic Journal of Combinatorics | ||||
ISSN: | 1077-8926 | ||||
Official Date: | 13 March 2009 | ||||
Dates: |
|
||||
Volume: | Vol.16 | ||||
Number: | No.1 | ||||
Number of Pages: | 11 | ||||
Page Range: | Article no. R35 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |