scientific article; zbMATH DE number 1099508
A class \(X\) of graphs is called hereditary if each subgraph of an element of \(X\) belongs to \(X\). Let \(X_n\) be the set of graphs in \(X\) whose vertices are labelled with \(1,2,\dots ,n\). It is known that, for every infinite hereditary class \(X\) different from the class of all graphs, the equation \(\log_2|X_n|=\bigl( 1-\frac 1{c(X)}\bigr) \frac{n^2}2+o(n^2)\) holds, where \(c(X)\) is a natural number [see \textit{V. E. Alekseev}, Diskretn. Mat. 4, No. 2, 148-157 (1992; Zbl 0766.05088) and \textit{V. E. Alekseev}, Discrete Math. Appl. 3, No. 2, 191-199 (1993; Zbl 0797.05077)]. The set of hereditary classes \(X\) such that \(c(X)=1\) is called a unitary layer. In the article, the lowest four levels of the unitary layer are studied for which the order of magnitude of \(\log_2|X_n|\) is one of the following: 1, \(\log_2 n\), \(n\), or \(n\log_2 n\). It is shown that no intermediate type of behavior can exist. The first three levels are described completely and all minimal elements are found for all the four levels.
- A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
- Hereditary classes of graphs: a parametric approach
- Stable-\(\Pi\) partitions of graphs
- On estimation of the number of graphs in some hereditary classes
- Range of values of the entropy of hereditary classes of graphs
- Locally bounded coverings and factorial properties of graphs
- On factorial properties of chordal bipartite graphs
- On the entropy of hereditary classes of coloured graphs
- scientific article; zbMATH DE number 1564004 (Why is no real title available?)
- Implicit representations and factorial properties of graphs
- Boundary properties of factorial classes of graphs
- Boundary properties of graphs for algorithmic graph problems
- Deciding the Bell number for hereditary graph properties
- Between 2- and 3-colorability
- The structure and the number of \(P_7\)-free bipartite graphs
- The structure and the number of \(P_7\)-free bipartite graphs
- Small but unwieldy: a lower bound on adjacency labels for small classes
- A polynomial Ramsey statement for bounded VC-dimension
- Tight bounds on adjacency labels for monotone graph classes
- Typical structure of hereditary graph families. I: Apex-free families
- Recent developments on graphs of bounded clique-width
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4369478)