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

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

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

 © Sobolev Institute of Mathematics, 2015