Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649396 | Discrete Mathematics | 2010 | 12 Pages |
Abstract
We consider vertex colorings of hypergraphs in which lower and upper bounds are prescribed for the largest cardinality of a monochromatic subset and/or of a polychromatic subset in each edge. One of the results states that for any integers sâ¥2 and aâ¥2 there exists an integer f(s,a) with the following property. If an interval hypergraph admits some coloring such that in each edge Ei at least a prescribed number siâ¤s of colors occur and also each Ei contains a monochromatic subset with a prescribed number aiâ¤a of vertices, then a coloring with these properties exists with at most f(s,a) colors. Further results deal with estimates on the minimum and maximum possible numbers of colors and the time complexity of determining those numbers or testing colorability, for various combinations of the four color bounds prescribed. Many interesting problems remain open.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Csilla Bujtás, Zsolt Tuza,