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: Pattern Hypergraphs. | Pattern Hypergraphs Zdenek Dvorak Jan Kara Daniel Kral Ondrej Pangrac Department of Applied Mathematics and Institute for Theoretical Computer Science Faculty of Mathematics and Physics Charles University Malostranske nam. 25 118 00 Prague Czech Republic. rakdver kara kral pangrac @ Submitted Feb 5 2008 Accepted Jan 7 2010 Published Jan 14 2010 Mathematics Subject Classification 05C15 secondary 05C65 Abstract The notion of pattern hypergraph provides a unified view of several previously studied coloring concepts. A pattern hypergraph H is a hypergraph where each edge is assigned a type n that determines which of possible colorings of the edge are proper. A vertex coloring of H is proper if it is proper for every edge. In general the set of integers k such that H can be properly colored with exactly k colors need not be an interval. We find a simple sufficient and necessary condition on the edge types Hl . nA for the existence of a pattern hypergraph H with edges of types Hl . nA such that the numbers of colors in proper colorings of H do not form an interval of integers. 1 Introduction Coloring problems are among the most intensively studied combinatorial problems both for the theoretical and the practical reasons. Generalizations of usual graph and hypergraph coloring . the channel assignment problem are widely applied in practice. A new general concept of mixed hypergraphs has attracted a lot of attention as witnessed by a recent monograph by Voloshin 29 and an enormous number of papers on the The research was partially supported by the grant GA CR 201 09 0197 The author has been supported by a Marie Curie Fellowship of the European Community programme Combinatorics Geometry and Computation under contract number HPMT-CT-2001-00282. Institute for Theoretical Computer Science ITI is supported by Ministry of Education of Czech Republic as projects 1M0545. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R15 1 subject . 6 10 13 17-24 26 30-33 . .
