Geodesic
Clique-width and the speed of hereditary properties
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper, we study the relationship between the number of $n$-vertex graphs in a hereditary class $\cal X$, also known as the speed of the class $\cal X$, and boundedness of the clique-width in this class. We show that if the speed of $\cal X$ is faster than $n!c^n$ for any $c$, then the clique-width of graphs in $\cal X$ is unbounded, while if the speed does not exceed the Bell number $B_n$, then the clique-width is bounded by a constant. The situation in the range between these two extremes is more complicated. This area contains both classes of bounded and unbounded clique-width. Moreover, we show that classes of graphs of unbounded clique-width may have slower speed than classes where the clique-width is bounded.
DOI : 10.37236/124
Classification : 05C75, 05C69, 05C85, 05A16
Mots-clés : clique-width, hereditary class of graphs, speed of hereditary classes, rates of growth, discrete layers 
@article{10_37236_124,
     author = {Peter Allen and Vadim Lozin and Micha\"el Rao},
     title = {Clique-width and the speed of hereditary properties},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/124},
     zbl = {1182.05101},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/124/}
}
TY  - JOUR
AU  - Peter Allen
AU  - Vadim Lozin
AU  - Michaël Rao
TI  - Clique-width and the speed of hereditary properties
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/124/
DO  - 10.37236/124
ID  - 10_37236_124
ER  - 
%0 Journal Article
%A Peter Allen
%A Vadim Lozin
%A Michaël Rao
%T Clique-width and the speed of hereditary properties
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/124/
%R 10.37236/124
%F 10_37236_124
Peter Allen; Vadim Lozin; Michaël Rao. Clique-width and the speed of hereditary properties. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/124

Cité par Sources :