Pattern Hypergraphs

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 $\Pi_i$ 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 $\Pi_1,\ldots,\Pi_\lambda$ for the existence of a pattern hypergraph $H$ with edges of types $\Pi_1,\ldots,\Pi_\lambda$ such that the numbers of colors in proper colorings of $H$ do not form an interval of integers.