Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A note on the speed of hereditary graph properties. | A note on the speed of hereditary graph properties Vadim V. Lozin DIMAP and Mathematics Institute University of Warwick Coventry CV4 7AL UK Colin Mayhill Victor Zamaraev Mathematics Institute University of Nizhny Novgorod Russia University of Warwick Coventry CV4 7AL UK Viktor. Zamaraev@gmail. com Submitted Jan 27 2011 Accepted Jul 27 2011 Published Aug 5 2011 Mathematics Subject Classification 05C30 Abstract For a graph property X let Xn be the number of graphs with vertex set 1 . n having property X also known as the speed of X. A property X is called factorial if X is hereditary . closed under taking induced subgraphs and ncin Xn nc2n for some positive constants C1 and c2. Hereditary properties with the speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored although this family includes many properties of theoretical or practical importance such as planar graphs or graphs of bounded vertex degree. To simplify the study of factorial properties we propose the following conjecture the speed of a hereditary property X is factorial if and only if the fastest of the following three properties is factorial bipartite graphs in X co-bipartite graphs in X and split graphs in X . In this note we verify the conjecture for hereditary properties defined by forbidden induced subgraphs with at most 4 vertices. Keywords Hereditary class of graphs Speed of hereditary properties Factorial class Research of this author was supported by the Centre for Discrete Mathematics and Its Applications DIMAP University of Warwick. Research of this author was supported by RFFI project number 11-01-00107-a and by FAP Research and educational specialists of innovative Russia project number THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P157 1 1 Introduction A graph property is an infinite class of graphs closed under isomorphism. A .
