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.

Research output not available from this repository, contact author.

Request Changes to record.

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:	Date Event 13 March 2009 Published
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