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: Counting Connected Set Partitions of Graphs. | Counting Connected Set Partitions of Graphs Frank Simon Peter Tittmannf and Martin Trinks Faculty Mathematics Sciences Computer Science University Mittweida Mittweida Germany Submitted Jun 14 2010 Accepted Jan 5 2011 Published Jan 12 2011 Mathematics Subject Classification 05C31 Abstract Let G V E be a simple undirected graph with n vertices then a set partition n V1 . Vk of the vertex set of G is a connected set partition if each subgraph G Vj induced by the blocks Vj of n is connected for 1 j k. Define qi G as the number of connected set partitions in G with i blocks. The partition polynomial is Q G x FXo qi G xi. This paper presents a splitting approach to the partition polynomial on a separating vertex set X in G and summarizes some properties of the bond lattice. Furthermore the bivariate partition polynomial Q G x y Mn 2m 1 qij G xiyj is briefly discussed where qij G counts the number of connected set partitions with i blocks and j intra block edges. Finally the complexity for the bivariate partition polynomial is proven to be P-hard. Keywords graph theory bond lattice chromatic polynomial splitting formula bounded treewidth yP-hard 1 Introduction One of the best-studied graph polynomials is the chromatic polynomial P G x giving the number of proper vertex colorings of an undirected graph G V E with at most x colors see . 2 8 9 12 11 . Rota 3 showed that the chromatic polynomial of a graph G is uniquely defined by its bond lattice nc G . The bond lattice can be defined as a sublattice of the partition lattice n V on V. A set partition n G n V belongs to nc G iff all blocks of n induce connected subgraphs of G. Email simon@ lEmail peter@ Email trinks@ THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P14 1 We investigate here the rank-generating function of nc G which we call the partition polynomial Q G x . There are two ways to consider Q G x namely from an order-theoretic point of view as rank-generating .