Clique-width and the speed of hereditary properties

摘要

a hereditary class X, also known as the speed of the class X, and boundedness ofthe clique-width in this class. We show that if the speed of X is faster than n!cn forany c, then the clique-width of graphs in X is unbounded, while if the speed doesnot 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. Thisarea contains both classes of bounded and unbounded clique-width. Moreover, weshow that classes of graphs of unbounded clique-width may have slower speed thanclasses where the clique-width is bounded.