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

A note on the speed of hereditary graph properties

Tools
- Tools
+ Tools

Lozin, Vadim V., Mayhill, Colin and Zamaraev, Victor (2011) A note on the speed of hereditary graph properties. The Electronic Journal of Combinatorics, Vol.18 (No.1). p. 157. ISSN 2150-959X.

[img]
Preview
PDF
WRAP_Lozin_v18i1p157.pdf - Published Version - Requires a PDF viewer.

Download (207Kb)
Official URL: http://www.combinatorics.org/ojs/index.php/eljc/ar...

Request Changes to record.

Abstract

For a graph property X, let X(n) be the number of graphs with vertex set {1, ..., n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and n(c1n) <= X(n) <= n(c2n) for some positive constants c(1) and c(2). Hereditary properties with the speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored, although this family includes many properties of theoretical or practical importance, such as planar graphs or graphs of bounded vertex degree. To simplify the study of factorial properties,we propose the following conjecture: the speed of a hereditary property X is factorial if and only if the fastest of the following three properties is factorial: bipartite graphs in X, co-bipartite graphs in X and split graphs in X. In this note, we verify the conjecture for hereditary properties defined by forbidden induced subgraphs with at most 4 vertices.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH): Graph theory
Journal or Publication Title: The Electronic Journal of Combinatorics
Publisher: Electronic Journal of Combinatorics
ISSN: 2150-959X
Official Date: August 2011
Dates:
DateEvent
August 2011Published
Volume: Vol.18
Number: No.1
Number of Pages: 14
Page Range: p. 157
Status: Peer Reviewed
Publication Status: Published
Date of first compliant deposit: 18 December 2015
Date of first compliant Open Access: 18 December 2015
Funder: University of Warwick. Centre for Discrete Mathematics and Its Applications, Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFBR), FAP
Grant number: 11-01-00107-a (RFFI), 2010-1.3.1-111-017-012 (FAP)

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

Downloads

Downloads per month over past year

View more statistics

twitter

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