Clique-width and the speed of hereditary properties (Q1010945)

Summary: We study the relationship between the number of \(n\)-vertex graphs in a hereditary class \(\mathcal X\), also known as the speed of the class \(\mathcal X\), and boundedness of the clique-width in this class. We show that if the speed of \(\mathcal X\) is faster than \(n!c^n\) for any \(c\), then the clique-width of graphs in \(\mathcal 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.