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

D. A. Shabanov ; T. M. Shaikheeva

Matematičeskie zametki, Tome 107 (2020) no. 3, pp. 454-465.

Résumé

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

Détail

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

Bibliographie

[1] V. G. Vizing, “Raskraska vershin grafa v predpisannye tsveta”, Metody diskretnogo analiza v teorii kodov i skhem, 29, In-t matem. SO AN SSSR, Novosibirsk, 1976, 3–10

[2] P. Erdős, A. L. Rubin, H. Taylor, “Choosability in graphs”, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Congress. Numer., 26, Utilitas Mathematica Publ., Winnipeg, Manitoba, 1980, 125–157 | MR

[3] N. Alon, “Choice number of graphs: a probabilistic approach”, Combin. Probab. Comput., 1:2 (1992), 107–114 | DOI | MR

[4] N. Gazit, M. Krivelevich, “On the asymptotic value of the choice number of complete multi-partite graphs”, J. Graph Theory, 52:2 (2006), 123–134 | DOI | MR

[5] D. A. Shabanov, “On a generalization of Rubin's theorem”, J. Graph Theory, 67:3 (2011), 226–234 | DOI | MR

[6] P. Haxell, J. Verstraëte, “List coloring hypergraphs”, Electron. J. Combin., 17:1 (2010), Research paper No 129 | MR

[7] P. Erdős, “On a combinatorial problem. II”, Acta Math. Acad. Sci. Hungar., 15:3-4 (1964), 445–447 | MR

[8] J. Radhakrishnan, A. Srinivasan, “Improved bounds and algorithms for hypergraph two-coloring”, Random Structures Algorithms, 16:1 (2000), 4–32 | MR

[9] A. M. Raigorodskii, D. A. Shabanov, “Zadacha Erdesha–Khainala o raskraskakh gipergrafov, ee obobscheniya i smezhnye problemy”, UMN, 66:5 (401) (2011), 109–182 | DOI | MR | Zbl

[10] D. Cherkashin, “A note on panchromatic colorings”, Discrete Math., 341:3 (2018), 652–657 | DOI | MR

[11] D. A. Kravtsov, N. E. Krokhmal, D. A. Shabanov, “Polnotsvetnye raskraski sluchainykh gipergrafov”, Diskret. matem., 31:2 (2019), 84–113 | DOI | MR

[12] D. Kravtsov, N. Krokhmal, D. Shabanov, “Panchromatic 3-colorings of random hypergraphs”, European J. Combin., 78 (2019), 28–43 | DOI | MR

[13] A. Kostochka, “On a theorem by Erdős, Rubin and Taylor on choosability of complete bipartite graphs”, Electron. J. Combin., 9:1 (2002), Note 9 | MR

[14] M. Akhmejanova, D. Shabanov, “Colorings of $b$-simple hypergraphs”, Electronic Notes in Discrete Math., 61 (2017), 29–35 | DOI

[15] A. Kupavskii, D. Shabanov, “Colourings of uniform hypergraphs with large girth and applications”, Combin. Probab. Comput., 27:2 (2018), 245–273 | DOI | MR

[16] M. B. Akhmejanova, D. A. Shabanov, “Equitable colorings of hypergraphs with few edges”, Discrete Appl. Math., 2019 (to appear) | DOI

[17] J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236 | DOI | MR

[18] D. Cherkashin, F. Petrov, “On small $n$-uniform hypergraphs with positive discrepancy”, J. Combin. Theory Ser. B, 139 (2019), 353–359 | DOI | MR

[19] A. Semenov, D. Shabanov, “On the weak chromatic number of random hypergraphs”, Discrete Appl. Math., 2019 (to appear) | DOI

[20] D. Cherkashin, J. Kozik, “A note on random greedy coloring of uniform hypergraphs”, Random Structures Algorithms, 47:3 (2015), 407–413 | DOI | MR

[21] I. Akolzin, D. Shabanov, “Colorings of hypergraphs with large number of colors”, Discrete Math., 339:12 (2016), 3020–3031 | DOI | MR

[22] A. E. Balobanov, D. A. Shabanov, “O chisle nezavisimykh mnozhestv v prostykh gipergrafakh”, Matem. zametki, 103:1 (2018), 38–48 | DOI