• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Around Erdos-Lovasz problem on colorings of non-uniform hypergraphs

Discrete Mathematics. 2015. Vol. 338. No. 11. P. 1976-1981.

The work deals with combinatorial problems concerning colorings of non-uniform hypergraphs. Let $H=(V,E)$ be a hypergraph with minimum edge-cardinality $n$. We show that if $H$ is a simple hypergraph (i.e. every two distinct edges have at most one common vertex) and
$$
  \sum_{e\in E}r^{1-|e|}\leqslant c\sqrt{n},
$$
for some absolute constant $c>0$, then $H$ is $r$-colorable. We also obtain a stronger result for triangle-free simple hypergraphs by proving that if $H$ is a simple triangle-free hypergraph and
$$
  \sum_{e\in E}r^{1-|e|}\leqslant c\cdot n,
$$
for some absolute constant $c>0$, then $H$ is $r$-colorable.