19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Mycielsky type construction for hypergraphs concerning fractional chromatic number

Presented by Mrs. Johana LUVIANO
Type: Oral presentation
Track: Coloring of Graphs


It is known the existence of sparse hypergraphs with hight chromatic number. A classical measure of sparseness is the clique number. The fractional chromatic number lies between the clique number and the chromatic number. In this work we prove the existence of uniform hypergraphs with fixed clique number and arbi\-tra\-ri\-ly large fractional chromatic number. Our proof is constructive and provides, in particular, as the Mycielsky construction does, a family of $r$-uniform hypergraphs without complete $r$-hypergraphs of order $r + 1$, and hight (fractional) chromatic number. We shall remark that our construction is not a straightforward generalization of Mycielsky's. Finally we describe, by forbidden induced subgraphs, classes of $2$ and $3$-uniform hypergraphs with chromatic number upper bounded by a linear function of its clique number.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors