Article ID Journal Published Year Pages File Type
4646608 Discrete Mathematics 2016 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,