?
On factorial properties of chordal bipartite graphs
Для класса графов X через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями числа n-вершинных графов хорошо изучены. Ситуация с факториальными классами существенно сложнее и менее изучена. В качестве одного из подходов к исследованию факториальных классов, в данной работе рассматриваются минимальные сверхфакториальные классы. В [J.P. Spinrad, Nonredundant 1's in Γ-free matrices, SIAM Journal on Discrete Mathematics, 8 (1995) 251--257], Спинрад показал, что число n-вершинных хордальных двудольных графов равно 2Θ(n log2n), то есть данный класс – сверхфакториальный. С другой стороны, все известные из литературы наследственные подклассы класса хордальных двудольных графов являются факториальными. Помимо лесов, к ним, в частности, относятся двудольные перестановочные графы, двудольные вполне сепарабельные графы, выпуклые графы. В данной работе изучаются новые наследственные подклассы класса хордальных двудольных графов и среди них выявляются как факториальные, так и сверхфакториальные. Последний результат показывает, что класс хордальных двудольных графов не является минимальным сверхфакториальным. Поиск минимальных сверхфакториальных подклассов класса хордальных двудольных графов остается открытым вопросом.