Color-bounded hypergraphs, IV: Stable colorings of hypertrees |
| |
Authors: | Csilla Bujtás Zsolt Tuza |
| |
Institution: | a Department of Computer Science, University of Pannonia, H-8200 Veszprém, Egyetem u. 10, Hungary b Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary |
| |
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. |
| |
Keywords: | Hypergraph coloring Interval hypergraph Hypertree Mixed hypergraph Stably bounded hypergraph Algorithmic complexity |
本文献已被 ScienceDirect 等数据库收录! |
|