\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Peter Allen, Vadim Lozin and Micha\"el Rao }
%
%
\medskip
\noindent
%
%
{\bf Clique-Width and the Speed of Hereditary Properties}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.



\bye