Volume 20, No 6, 2013, P. 3039
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, cobipartite 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
email: viktor.zamaraev@gmail.com
