Geodesic
On factorial subclasses of $K_{1,3}$-free graphs
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 30-39 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DA_2013_20_6_a2,
     author = {V. A. Zamaraev},
     title = {On factorial subclasses of $K_{1,3}$-free graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {30--39},
     year = {2013},
     volume = {20},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_6_a2/}
}
TY  - JOUR
AU  - V. A. Zamaraev
TI  - On factorial subclasses of $K_{1,3}$-free graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 30
EP  - 39
VL  - 20
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_6_a2/
LA  - ru
ID  - DA_2013_20_6_a2
ER  - 
%0 Journal Article
%A V. A. Zamaraev
%T On factorial subclasses of $K_{1,3}$-free graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 30-39
%V 20
%N 6
%U http://geodesic.mathdoc.fr/item/DA_2013_20_6_a2/
%G ru
%F DA_2013_20_6_a2
V. A. Zamaraev. On factorial subclasses of $K_{1,3}$-free graphs. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 30-39. http://geodesic.mathdoc.fr/item/DA_2013_20_6_a2/

[1] Alekseev V. E., “Oblast znachenii entropii nasledstvennykh klassov grafov”, Diskret. matematika, 4:2 (1992), 148–157 | MR | Zbl

[2] Alekseev V. E., “O nizhnikh yarusakh reshëtki nasledstvennykh klassov grafov”, Diskret. analiz i issled. operatsii. Ser. 1, 4:1 (1997), 3–12 | MR | Zbl

[3] Zamaraev V. A., “Otsenka chisla grafov v nekotorykh nasledstvennykh klassakh”, Diskret. matematika, 23:3 (2011), 57–62 | DOI | MR | Zbl

[4] Balogh J., Bollobás B., Weinreich D., “The speed of hereditary properties of graphs”, J. Comb. Theory. Ser. B, 79 (2000), 131–156 | DOI | MR | Zbl

[5] Cayley A., “A theorem on trees”, Quart. J. Math., 23 (1889), 376–378

[6] Faenza Y., Oriolo G., Stauffer G., “An algorithmic decomposition of claw-free graphs leading to an $O(n^3)$-algorithm for the weighted stable set problem”, Proc. 22nd ACM-SIAM Symp. Discrete Algorithms 2011 (San Francisco, January 23–25, 2011), SIAM, Philadelphia, 2011, 630–646 | MR

[7] Lozin V. V., Mayhill C., Zamaraev V., “A note on the speed of hereditary graph properties”, Electron. J. Comb., 18:1 (2011), 1–14 | MR | Zbl

[8] Lozin V. V., Mayhill C., Zamaraev V., “Locally bounded coverings and factorial properties of graphs”, Eur. J. Comb., 33:4 (2012), 534–543 | DOI | MR | Zbl

[9] Scheinerman E. R., Zito J., “On the size of hereditary classes of graphs”, J. Comb. Theory. Ser. B, 61 (1994), 16–39 | DOI | MR | Zbl

[10] Zamaraev V., “Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph”, Moscow J. Comb. Number Theory, 1:3 (2011), 277–286 | MR