This article is cited in 2 papers

The List-Chromatic Number of Complete Multipartite Hypergraphs and Multiple Covers by Independent Sets

D. A. Shabanov^abc, T. M. Shaikheeva<sup>b

a</sup> Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
^b Lomonosov Moscow State University
^c National Research University "Higher School of Economics", Moscow

Abstract: This paper deals with list colorings of uniform hypergraphs. Let $H(m,r,k)$ be the complete $r$-partite $k$-uniform hypergraph with parts of equal size $m$ in which each edge contains exactly one vertex from some $k\le r$ parts. Using results on multiple covers by independent sets, we establish that, for fixed $k$ and $r$, the list-chromatic number of $H(m,r,k)$ is $(1+o(1))\log_{r/(r-k+1)}(m)$ as $m\to\infty$.

Keywords: hypergraphs, independent sets, list colorings, multiple covers.

UDC: 519.179.1+519.174.7+519.174.3

Received: 17.03.2019
Revised: 16.07.2019

DOI: 10.4213/mzm12379

 English version: Mathematical Notes, 2020, 107:3, 499–508

Bibliographic databases:

• 
• 
• 
•