A note on the speed of hereditary graph properties

MaRDI QIDQ640407zbMATH OpenFDO

Authors Vadim Lozin, Colin Mayhill, Victor Zamaraev

Publication date 18 October 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p157.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

factorial classhereditary class of graphsspeed of hereditary properties

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75)

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.

Recommendations

• The speed of hereditary properties of graphs
• The structure of almost all graphs in a hereditary property
• Hereditary and monotone properties of combinatorial structure
• On the size of hereditary classes of graphs
• Locally bounded coverings and factorial properties of graphs

Cited in

(14)

• On the size of hereditary classes of graphs
• On the speed of algebraically defined graph classes
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• Locally bounded coverings and factorial properties of graphs
• On factorial properties of chordal bipartite graphs
• Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph
• \(\mathrm{VC}_{\ell }\)-dimension and the jump to the fastest speed of a hereditary \(\mathcal {L}\)-property
• Implicit representations and factorial properties of graphs
• Boundary properties of factorial classes of graphs
• On factorial subclasses of \(K_{1,3}\)-free graphs
• Deciding the Bell number for hereditary graph properties
• The structure and the number of \(P_7\)-free bipartite graphs
• The structure and the number of \(P_7\)-free bipartite graphs
• Hereditary properties of partitions, ordered graphs and ordered hypergraphs

This page was built for publication: A note on the speed of hereditary graph properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640407)