Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Mat. Zametki, 2020, Volume 107, Issue 3, Pages 454–465 (Mi mz12379)  

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

D. A. Shabanovabc, T. M. Shaikheevab

a 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.

Funding Agency Grant Number
National Research University Higher School of Economics
The article was prepared within the framework of the Basic Research Program at National Research University Higher School of Economics.


DOI: https://doi.org/10.4213/mzm12379

Full text: PDF file (526 kB)
First page: PDF file
References: PDF file   HTML file

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

Bibliographic databases:

UDC: 519.179.1+519.174.7+519.174.3
Received: 17.03.2019
Revised: 16.07.2019

Citation: D. A. Shabanov, T. M. Shaikheeva, “The List-Chromatic Number of Complete Multipartite Hypergraphs and Multiple Covers by Independent Sets”, Mat. Zametki, 107:3 (2020), 454–465; Math. Notes, 107:3 (2020), 499–508

Citation in format AMSBIB
\Bibitem{ShaSha20}
\by D.~A.~Shabanov, T.~M.~Shaikheeva
\paper The List-Chromatic Number of Complete Multipartite Hypergraphs and Multiple Covers by Independent Sets
\jour Mat. Zametki
\yr 2020
\vol 107
\issue 3
\pages 454--465
\mathnet{http://mi.mathnet.ru/mz12379}
\crossref{https://doi.org/10.4213/mzm12379}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=4070865}
\elib{https://elibrary.ru/item.asp?id=43286398}
\transl
\jour Math. Notes
\yr 2020
\vol 107
\issue 3
\pages 499--508
\crossref{https://doi.org/10.1134/S000143462003013X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000528213700013}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85083862949}


Linking options:
  • http://mi.mathnet.ru/eng/mz12379
  • https://doi.org/10.4213/mzm12379
  • http://mi.mathnet.ru/eng/mz/v107/i3/p454

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Математические заметки Mathematical Notes
    Number of views:
    This page:159
    References:10
    First page:3

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021