کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647763 | 1342373 | 2013 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the cc-strong chromatic number of tt-intersecting hypergraphs On the cc-strong chromatic number of tt-intersecting hypergraphs](/preview/png/4647763.png)
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.
Journal: Discrete Mathematics - Volume 313, Issue 10, 28 May 2013, Pages 1063–1069