This article is cited in 1 paper

On factorial subclasses of $K_{1,3}$-free graphs

V. A. Zamaraev<sup>ab

a</sup> University of Nizhni Novgorod, 23 Gagarin Ave., 603950 Nizhni Novgorod, Russia
^b National Research University Higher School of Economics, 136 Rodionov St., 603093 Nizhni Novgorod, Russia

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.

UDC: 519.1

Received: 23.10.2012
Revised: 09.03.2013

Bibliographic databases:

•