کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646608 | 1342307 | 2016 | 7 صفحه PDF | دانلود رایگان |

The problem of computing the chromatic number of Kneser hypergraphs has been extensively studied over the last 40 years and the fractional version of the chromatic number of Kneser hypergraphs is only solved for particular cases. The (p,q)(p,q)-extremal problem is to maximize the number of edges in a kk-uniform hypergraph HH with given order subject to the constraint that any pp edges contain qq edges that have a vertex in common. In this paper we found a link between the fractional chromatic number of Kneser hypergraphs and the (p,q)(p,q)-extremal problem. We solve the (p,q)(p,q)-extremal problem for graphs and with the aid of this result we calculate the fractional chromatic number of Kneser hypergraphs when they are composed with sets of cardinality 2.
Journal: Discrete Mathematics - Volume 339, Issue 11, 6 November 2016, Pages 2819–2825