The Library

A note on the speed of hereditary graph properties

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

Preview

PDF
WRAP_Lozin_v18i1p157.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (207Kb)

Official URL: http://www.combinatorics.org/ojs/index.php/eljc/ar...

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 > 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:

Date	Event
August 2011	Published

Volume:

Vol.18

Number:

No.1

Number of Pages:

Page Range:

p. 157

Status:

Peer Reviewed

Publication Status:

Published

Funder:

University of Warwick. Centre for Discrete Mathematics and Its Applications, Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFBR), FAP

Grant number:

11-01-00107-a (RFFI), 2010-1.3.1-111-017-012 (FAP)

References:

[1] V.E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskret.
Mat. 4 (1992), no. 2, 148–157 (in Russian; translation in Discrete Mathematics and
Applications, 3 (1993), no. 2, 191–199).
[2] V. Alekseev, On lower layers of the lattice of hereditary classes of graphs,
Diskretn. Anal. Issled. Oper. Ser. 1 Vol. 4 ,no. 1, (1997), 3-12 (in Russian).
[3] P. Allen, Forbidden induced bipartite graphs, Journal of Graph Theory, 60 (2009)
219–241.
[4] P. Allen, V. Lozin and M. Rao, Clique-width and the speed of hereditary prop-
erties, Electronic Journal of Combinatorics, 16 (2009) Research Paper 35.
[5] J. Balogh, B. Bollob´as and D. Weinreich, The speed of hereditary properties
of graphs, J. Combin. Theory B, 79 (2000) 131-156.
[6] J. Balogh, B. Bollob´as and D. Weinreich, A jump to the Bell number for
hereditary graph properties, J. Combin. Theory Ser. B 95 (2005) 29–48.
[7] A. Brandst¨adt, J. Engelfriet, H.-O. Le and V.V. Lozin, Clique-Width for
4-Vertex Forbidden Subgraphs Theory of Computing Systems, 34 (2006) 561–590.
[8] P. Cameron, T. Prellberg and D. Stark, Asymptotic enumeration of 2-covers
and line graphs, Discrete Mathematics, 310 (2010) 230–240.
[9] M. Chudnovsky and P. Seymour, The structure of claw-free graphs, London.
Math. Soc. Lecture Note Series, 327 (2005) 153-171.
[10] F. Eisenbrand, G. Oriolo, G. Stauffer and P. Ventura, The stable set
polytope of quasi-line graphs, Combinatorica, 28 (2008) 45–67.
[11] T. Kloks, K1,3-free and W4-free graphs, Information Processing Letters, 60 (1996)
221–223.
[12] S. Norine, P. Seymour, R. Thomas and P. Wollan, Proper minor-closed
families are small, J. Combinatorial Theory B 96 (2006) 754–757.
[13] E.R. Scheinerman and J. Zito, On the size of hereditary classes of graphs,
J. Combin. Theory B 61 (1994) 16–39.
[14] J.P. Spinrad, Nonredundant 1’s in -free matrices, SIAM J. Discrete Math. 8
(1995) 251–257.
[15] S. Wagon, A bound on the chromatic number of graphs without certain induced
subgraphs, J. Combinatorial Theory B 29 (1980) 345–346.