Allen, Peter, Lozin, Vadim 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

Full text not available from this repository.

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 > Mathematics
Journal or Publication Title:	Electronic Journal of Combinatorics
Publisher:	Electronic Journal of Combinatorics
ISSN:	1077-8926
Date:	13 March 2009
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
URI:	http://wrap.warwick.ac.uk/id/eprint/28293

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item