Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647763 | Discrete Mathematics | 2013 | 7 Pages |
For a fixed c≥2c≥2, a cc-strong coloring of the hypergraph GG is a vertex coloring such that each edge ee of GG covers vertices with at least min{c,|e|}min{c,|e|} distinct colors. A hypergraph istt-intersecting if the intersection of any two of its edges contains at least tt vertices. This paper addresses the question: what is the minimum number of colors which suffices to cc-strong color any tt-intersecting hypergraph? We first show that the number of colors required to cc-strong color a hypergraph of size nn is O(n). Then we prove that we can use finitely many colors to 3-strong color any 2-intersecting hypergraph. Finally, we show that 2c−12c−1 colors are enough to cc-strong color any shifted (c−1)(c−1)-intersecting hypergraph, and 2c−22c−2 colors are enough to cc-strong color any shifted tt-intersecting hypergraph for t≥ct≥c. Both chromatic numbers are optimal and match conjectured statements in which the shifted condition is removed.