Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Clique-width and the speed of hereditary properties

Tools
- Tools
+ 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.

Research output not available from this repository, contact author.
Official URL: http://www.combinatorics.org/Volume_16/v16i1toc.ht...

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:
DateEvent
13 March 2009Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us