Coloring hypergraphs with bounded cardinalities of edge intersections

Margarita Akhmejanova; Dmitry Shabanov

doi:10.1016/j.disc.2019.111692

paper

Coloring hypergraphs with bounded cardinalities of edge intersections

arXiv:1909.00448 · doi:10.1016/j.disc.2019.111692

Abstract

The paper deals with an extremal problem concerning colorings of hypergraphs with bounded edge degrees. Consider the family of $b$ -simple hypergraphs, in which any two edges do not share more than $b$ common vertices. We prove that for $n ⩾ n_{0} (b)$ , any $n$ -uniform $b$ -simple hypergraph with the maximum edge degree at most $c \cdot n r^{n - b}$ is $r$ -colorable, where $c > 0$ is an absolute constant. We also establish some applications of the main result.