?
A note on the speed of hereditary graph properties
Для класса графов X, через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями числа n-вершинных графов хорошо изучены. Ситуация с факториальными классами существенно сложнее и менее изучена. Вместе с тем, среди этих классов имеется много классов, представляющих интерес с практической и теоретической точек зрения, таких как планарные графы или графы с ограниченной степенью вершин. В качестве одного из подходов к исследованию факториальных классов предлагается следующая гипотеза: наследственный класс факториален тогда и только тогда, когда по крайней мере один из трех его подклассов: подкласс двудольных, подкласс кодвудольных и подкласс расщепляемых графов является факториальным и каждый из этих классов не более чем факториальный. В настоящей работе данная гипотеза доказывается для наследственных классов, у которых запрещенные графы содержат не больше 4 вершин.