Fractional hypergraph coloring

Abstract

We investigate proper $(a:b)$-fractional colorings of $n$-uniform hypergraphs, which generalize traditional integer colorings of graphs. Each vertex is assigned $b$ distinct colors from a set of $a$ colors, and an edge is properly colored if no single color is shared by all vertices of the edge. A hypergraph is $(a:b)$-colorable if every edge is properly colored. We prove that for any $2\le b\le a-2\le n/\ln n$, every $n$-uniform hypergraph $H$ with $|E(H)|\le (a{b}^3{)}^{-1/2}{\left(\frac{n}{\log n}\right)}^{1/2}{\left(\frac{a}{b}\right)}^{n-1}$ is proper $(a:b)$-colorable. We also address specific cases, including $(a:a-1)$-colorability.

10 pages, 1 figure