|
Diskretnyi Analiz i Issledovanie Operatsii, 2013, Volume 20, Issue 6, Pages 30–39
(Mi da751)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
On factorial subclasses of $K_{1,3}$-free graphs
V. A. Zamaraevab a 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.
Received: 23.10.2012 Revised: 09.03.2013
Citation:
V. A. Zamaraev, “On factorial subclasses of $K_{1,3}$-free graphs”, Diskretn. Anal. Issled. Oper., 20:6 (2013), 30–39
Linking options:
https://www.mathnet.ru/eng/da751 https://www.mathnet.ru/eng/da/v20/i6/p30
|
|