• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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.
Zamaraev V. A.

Для класса графов X, через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ X ≤ nc2n для некоторых положительных констант c1 и c2. Граф G называется квазиреберным, если окрестность каждой его вершины может быть разбита на две клики. В настоящей работе описываются почти все факториальные подклассы класса квазиреберных графов, определяемые одним запрещенным порожденным подграфом. Используя этот результат, в работе доказывается, что класс Free(K1,3,W4) факториальный, что обобщает один из результатов работы [8].