Clique-Width and the Speed of Hereditary Properties

Peter Allen 1 Vadim Lozin 1 Michaël Rao 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Article dans une revue
Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2009, 16 (1), pp.11
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00808010
Contributeur : Pascal Ochem <>
Soumis le : jeudi 4 avril 2013 - 17:02:21
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00808010, version 1

Collections

Citation

Peter Allen, Vadim Lozin, Michaël Rao. Clique-Width and the Speed of Hereditary Properties. Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2009, 16 (1), pp.11. 〈lirmm-00808010〉

Partager

Métriques

Consultations de la notice

65