Book chapter
Оценка числа графов в некоторых наследственных классах
С. 301-303.
We use cookies in order to improve the quality and usability of the HSE website. More information about the use of cookies is available here, and the regulations on processing personal data can be found here. By continuing to use the site, you hereby confirm that you have been informed of the use of cookies by the HSE website and agree with our rules for processing personal data. You may disable cookies in your browser settings.
✖For a graph property X, let Xn 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 nc1n ≤ Xn ≤ nc2n for some constants c1 and c2. Hereditary properties with speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored. Only the properties with speeds up to the Bell number are well studied and well behaved. To better understand the behavior of factorial properties with faster speeds we introduce a structural tool called locally bounded coverings and show that a variety of graph properties can be described by means of this tool.
For a graph property X, let Xn be the set of graphs with the vertex set {1, . . . , n} that satisfy the property X. A property X is called factorial if X is hereditary (i. e. closed under taking induced subgraphs) and nc1n ≤ X ≤ nc2n for some positive constants c1 and c2. A graph G is a quasi-line if for every vertex v, the set of neighbors of v can be expressed as a union of two cliques. In the present paper we identify almost all factorial subclasses of quasi-line graphs defined by one forbidden induced subgraph. We use these new results to prove that the class Free(K1,3,W4) is factorial, which improves on a result of Lozin, Mayhill and Zamaraev [8].