Volume 20, No 6, 2013, P. 30-39

UDC 519.1
Zamaraev V. A.
On factorial subclasses of $K_{1,3}$-free graphs

Abstract:
For a set of labeled graphs $X$, let $X_n$ be the set of $n$-vertex graphs from $X$. A hereditary class $X$ is called at most factorial if there exist positive constants $c$ and $n_0$ such that $|X_n|\leq n^{cn}$ for all $n>n_0$. Lozin's conjecture states that a hereditary class $X$ is at most factorial if and only if each of the following three classes is at most factorial: $X\cap B$, $X\cap\widetilde B$ and $X\cap S$, where $B,\widetilde B$ and $S$ are the classes of bipartite, co-bipartite and split graphs respectively. We prove this conjecture for subclasses of $K_{1,3}$-free graphs defined by two forbidden subgraphs.
Bibliogr. 10.

Keywords: hereditary class of graphs, factorial class.

Zamaraev Victor Andreevich ^1,2
1. University of Nizhni Novgorod,
23 Gagarin Ave., 603950 Nizhni Novgorod, Russia
2. National Research University Higher School of Economics,
136 Rodionov St., 603093 Nizhni Novgorod, Russia
e-mail: viktor.zamaraev@gmail.com