Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph

Moscow Journal of Combinatorics and Number Theory. 2011. Vol. 1. No. 3. P. 277–286.

Замараев В. А.

Для класса графов X, через X_n обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и n^c₁n ≤ X ≤ n^c₂n для некоторых положительных констант c₁ и c₂. Граф G называется квазиреберным, если окрестность каждой его вершины может быть разбита на две клики. В настоящей работе описываются почти все факториальные подклассы класса квазиреберных графов, определяемые одним запрещенным порожденным подграфом. Используя этот результат, в работе доказывается, что класс Free(K_1,3,W₄) факториальный, что обобщает один из результатов работы [8].

Ключевые слова: hereditary class of graphs, factorial class, наследственный класс графов, факториальный класс, quasi-line graphs, квазиреберные графы