A note on the speed of hereditary graph properties
type: Item
instance of: scholarly article
title: A note on the speed of hereditary graph properties
zbMATH Open document ID: 1230.05164
author: Vadim Lozin
author: Colin Mayhill
author: Victor Zamaraev
published in: The Electronic Journal of Combinatorics
publication date: 2011-10-18T00:00:00Z
full work available at URL: v18i1p157.html
review text: Summary: For a graph property \(X\), let \(X_n\) be the number of graphs with vertex set \(\{1, \ldots , 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^{c_1n} \leq X_n \leq n^{c_2n}\) 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.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5960019
zbMATH Keywords: hereditary class of graphs
zbMATH Keywords: speed of hereditary properties
zbMATH Keywords: factorial class
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5960019