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: An Extremal Property of Tur´n Graphs a. | An Extremal Property of Turan Graphs Felix Lazebnik Spencer Tofts Department of Mathematical Sciences University of Delaware Newark DE 19716 USA lazebnik@ tofts@ Submitted Jul 6 2010 Accepted Nov 19 2010 Published Dec 10 2010 Mathematics Subject Classification 05C15 05C30 05C31 05C35 Abstract Let Fn tr n denote the family of all graphs on n vertices and tr n edges where tr n is the number of edges in the Turan s graph Tr n - the complete r-partite graph on n vertices with partition sizes as equal as possible. For a graph G and a positive integer A let PG A denote the number of proper vertex colorings of G with at most A colors and let f n tr n A max PG A G E Fn tr n . We prove that for all n r 2 f n tr n r 1 PTr n r 1 and that Tr n is the only extremal graph. 1 Introduction All graphs in this paper are finite undirected and have neither loops nor multiple edges. For all missing definitions and facts which are mentioned but not proved we refer the reader to Bollobas 3 . For a graph G let V G and E G denote the vertex set of G and the edge set of G respectively. Let A denote the cardinality of a set A. Let n v G V G and m e G E G denote the number of vertices the order of G and number of edges the size of G respectively. An edge x y of G will also be denoted by xy or yx. For sets X Y let X Y X Y. For A c V G let G A denote the subgraph of G induced by A which means that V G A A and E G A consists of all edges xy of G with both x and y in A. For a vertex v of G let N v NG v u E V G uv E E G denote the neighborhood of v in G and d v dG v NG v denote the degree of v in G. For A c V G let dA v A n NG v denote the number of neighbors of a vertex v in G which are in A. For two disjoint nonempty subsets A B c V G by G A B This research was partially supported by the NSA Grant H98230-08-1-0041. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R170 1 we denote the bipartite subgraph of G such that V G A B A u B and E G A B consists of all edges of G with .
