tailieunhanh - Báo cáo toán hoc:" Some Results on Chromatic Polynomials of Hypergraphs"

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í toán học quốc tế đề tài:Some Results on Chromatic Polynomials of Hypergraphs. | Some Results on Chromatic Polynomials of Hypergraphs Manfred Walter SAP AG Dietmar-Hopp-Allee 16 D-69190 Walldorf Germany Postal Address Manfred Walter Schaelzigweg 35 D-68723 Schwetzingen Germany mwalter-schwetzingen@ Submitted Feb 11 2009 Accepted Jul 23 2009 Published Jul 31 2009 Mathematics Subject Classifications 05C15 05C65 Abstract In this paper chromatic polynomials of non-uniform hypercycles unicyclic hypergraphs hypercacti and sunflower hypergraphs are presented. The formulae generalize known results for r-uniform hypergraphs due to Allagan Borowiecki Lazuka Dohmen and Tomescu. Furthermore it is shown that the class of non-uniform hypertrees with m edges where mr edges have size r r 2 is chromatically closed if and only if m 4 m2 m 1. 1 Notation and preliminaries Most of the notation concerning graphs and hypergraphs is based on Berge 4 . A hypergraph H V E consists of a finite non-empty set V of vertices and a family E of edges which are non-empty subsets of V of cardinality at least 2. An edge e of cardinality r e is called an r-edge. H is r-uniform if each edge e E E is an r-edge. The degree dn v is the number of edges containing the vertex v. A vertex v is called pendant if dH v 1. H is said to be simple if all edges are distinct. H is is said to be Sperner if no edge is a subset of another edge. Uniform simple hypergraphs are Sperner. Simple 2-uniform hypergraphs are graphs. A hypergraph H W F with W c V and F c E is called a subhypergraph of H. If W ueeF e then the subhypergraph is said to be induced by F abbreviated by HF. The 2-section of a hypergraph H V E is the graph H 2 V E 2 such that u v E E 2 u v u v eV if and only if u v are contained in a hyperedge of H. In a hypergraph H V E an alternating sequence v1 e1 v2 e2 . em vm 1 where vi vj 1 i j m vi vi 1 E ei is called a chain. Note that repeated edges are THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R94 1 allowed in a chain. If also ei ej 1 i j m we call it a path of length m. If