Clique-Width and the Speed of Hereditary Properties - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2009

Clique-Width and the Speed of Hereditary Properties


In this paper, we study the relationship between the number of n-vertex graphs in a hereditary class X , also known as the speed of the class X , and boundedness of the clique-width in this class. We show that if the speed of X is faster than n!c^n for any c, then the clique-width of graphs in X is unbounded, while if the speed does not exceed the Bell number Bn , 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.

Dates and versions

lirmm-00808010 , version 1 (04-04-2013)



Peter Allen, Vadim Lozin, Michaël Rao. Clique-Width and the Speed of Hereditary Properties. The Electronic Journal of Combinatorics, 2009, 16 (1), pp.11. ⟨10.37236/124⟩. ⟨lirmm-00808010⟩
76 View
0 Download



Gmail Mastodon Facebook X LinkedIn More