tailieunhanh - Báo cáo toán học: "Clique-width and the speed of hereditary properties"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Clique-width and the speed of hereditary properties. | Clique-width and the speed of hereditary properties Peter Allen Vadim Lozin Michael Rao Ỉ Submitted Sep 30 2008 Accepted Mar 5 2009 Published Mar 13 2009 Mathematics Subject Classification 05A16 05C75 05C78 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 cn 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. Keywords Clique-width Hereditary class of graphs Speed of hereditary classes 1 Introduction Clique-width is a graph parameter which is of primary importance in algorithmic graph theory because many problems being NP-hard in general admit polynomial-time solutions when restricted to a class X of graphs where the clique-width is bounded by a constant 9 . In the study of clique-width we may assume without loss of generality that X is a hereditary class of graphs . a class closed under taking induced subgraphs because the clique-width of a graph cannot be less than the clique-width of any of its induced subgraphs. In a recent line of research it was shown that the growth of the number Xn of n-vertex graphs in a hereditary class X also known as the speed of the class is far from arbitrary. Specifically the rates of growth constitute discrete layers. Alekseev 1 and Scheinerman DIMAP and Mathematics Institute University of Warwick Coventry CV4 7AL UK. . This author gratefully acknowledges the support of DIMAP - Centre for Discrete Mathematics and its .