Том 20, номер 6, 2013 г., Стр. 30-39

УДК 519.1
Замараев В. А.
О факториальных подклассах класса графов без $K_{1,3}$

Аннотация:
Для множества помеченных графов $X$ через $X_n$ обозначается множество $n$-вершинных графов из $X$. Наследственный класс $X$ называется не более чем факториальным, если существуют положительные константы $c,n_0$ такие, что $|X_n|\leq n^{cn}$ для всех $n>n_0$. Гипотеза Лозина говорит о том, что наследственный класс $X$ не более чем факториальный тогда и только тогда, когда каждый из классов $X\cap B$, $X\cap\widetilde B$ и $X\cap S$ не более чем факториальный, где $B,\widetilde B$ и $S$ – классы двудольных, дополнительных к двудольным и расщепляемых графов соответственно. В работе данная гипотеза доказывается для подклассов класса $\mathrm Free(\{K_{1,3}\})$, определяемых двумя запрещёнными графами.
Библиогр. 10.

Ключевые слова: факториальный класс, наследственный класс графов.

Замараев Виктор Андреевич ^1,2
1. Нижегородский гос. университет,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
2. Нац. исслед. университет «Высшая школа экономики»,
ул. Родионова, 136, 603093 Нижний Новгород, Россия
е-mail: viktor.zamaraev@gmail.com

Статья поступила 23 октября 2012 г.
Исправленный вариант — 9 марта 2013 г.

Литература

[1] Алексеев В. Е. Область значений энтропии наследственных классов графов // Дискрет. математика. - 1992. - Т. 4, № 2. - С. 148–157.

[2] Алексеев В. Е. О нижних ярусах решётки наследственных классов графов // Дискрет. анализ и исслед. операций. Сер. 1. - 1997. - Т. 4, № 1. - С. 3–12.

[3] Замараев В. А. Оценка числа графов в некоторых наследственных классах // Дискрет. математика. - 2011. - Т. 23, № 3. - С. 57–62.

[4] Balogh J., Bollobás B., Weinreich D. The speed of hereditary properties of graphs // J. Comb. Theory. Ser. B. - 2000. - Vol. 79. - P. 131–156.

[5] Cayley A. A theorem on trees // Quart. J. Math. - 1889. - Vol. 23. - P. 376–378.

[6] Faenza Y., Oriolo G., Stauffer G. An algorithmic decomposition of clawfree graphs leading to an O(n3)-algorithm for the weighted stable set problem // Proc. 22nd ACM-SIAM Symp. Discrete Algorithms, 2011 (San Francisco, January 23–25, 2011). - Philadelphia: SIAM, 2011. - P. 630–646.

[7] Lozin V. V., Mayhill C., Zamaraev V. A note on the speed of hereditary graph properties // Electron. J. Comb. - 2011. - Vol. 18, N 1. - P. 1–14.

[8] Lozin V. V., Mayhill C., Zamaraev V. Locally bounded coverings and factorial properties of graphs // Eur. J. Comb. - 2012. - Vol. 33, N 4. - P. 534–543.

[9] Scheinerman E. R., Zito J. On the size of hereditary classes of graphs // J. Comb. Theory. Ser. B. - 1994. - Vol. 61. - P. 16–39.

[10] Zamaraev V. Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph // Moscow J. Comb. Number Theory. - 2011. - Vol. 1, N 3. - P. 277–286.