On list chromatic numbers of 2-colorable hypergraphs
Автор: Cherkashin D. D., Gordeev A. S.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 1 (53) т.14, 2022 года.
Бесплатный доступ
We give an upper bound on the list chromatic number of a 2-colorable hypergraph which generalizes the Schauz bound on k-partite k-uniform hypergraphs. It makes sense for sparse hypergraphs. In particular we show that a k-uniform k-regular hypergraph has the list chromatic number 2 for k ≥ 4. Also, we obtain both lower and upper bounds on the list chromatic number of a complete s-uniform 2-colorable hypergraph in the vein of the Erd˝os-Rubin-Taylor theorem.
List colorings, hypergraph colorings, erd˝os-rubin-taylor theorem
Короткий адрес: https://sciup.org/142235298
IDR: 142235298 | DOI: 10.53815/20726759_2022_14_1_49
Список литературы On list chromatic numbers of 2-colorable hypergraphs
- Akhmejanova M., Balogh J. Chain method for panchromatic colorings of hvpergraphs // arXiv preprint arXiv:2008.03827v3. 2020.
- Alon N. Combinatorial Nullstellensatz // Combinatorics, Probability and Computing. 1999. V. 8, N 1-2. P. 7-29.
- Alon N., Tarsi M. Colorings and orientations of graphs // Combinatorica. 1992. V. 12, N 2. P. 125-134.
- Alon N. Degrees and choice numbers // Random Structures k, Algorithms. 2000. V. 16, N 4. P. 364-368.
- Erdos P., Rubin A.L., Taylor H. Choosabilitv in graphs // Congr. Numer. 1979. V. 26. P. 125-157.
- Gravin N. V., Karpov D. V. On proper colorings of hvpergraphs // Zap. Nauchn. Sem. POMI. 2011. V. 391. P. 79-89.
- Henning M.A., Yeo A. 2-colorings in ^-regular fc-uniform hvpergraphs // European Journal of Combinatorics. 2013. V. 34, N 7. P. 1192-1202.
- Kostochka A. On a theorem of Erdos, Rubin, and Taylor on choosabilitv of complete bipartite graphs // The Electronic Journal of Combinatorics. 2002. V. 9, N 9. P. 1.
- Raigorodskii A.M., Cherkashin D.D. Extremal problems in hvpergraph colourings // Russian Mathematical Surveys. 2020. V. 75, N 1. P. 89-146.
- Schauz U. A paintabilitv version of the combinatorial Nullstellensatz, and list colorings of fc-partite fc-uniform hvpergraphs // The Electronic Journal of Combinatorics. 2010. P. R176.
- Thomassen C. The even cycle problem for directed graphs // Journal of the American Mathematical Society. 1992. V. 5, N 2. P. 217-229.
- Vizing V.G. Vertex colorings with given colors // Diskret. Analiz. 1976. V. 29. P. 3-10.
