Processing math: 100%
EN|RU

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

UDC 519.1
Zamaraev V. A.
On factorial subclasses of K1,3-free graphs

Abstract:
For a set of labeled graphs X, let Xn 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 n0 such that |Xn|ncn for all n>n0. 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: XB, X˜B and XS, where B,˜B and S are the classes of bipartite, co-bipartite and split graphs respectively. We prove this conjecture for subclasses of K1,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