О справедливых раскрасках простых гиперграфов
Автор: Акользин И.А.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 4 (36) т.9, 2017 года.
Бесплатный доступ
Исследуется проблема о справедливых раскрасках гиперграфов, связанная с теоре- мой Хайнала-Семереди. Получена новая оценка максимальной степени вершины про- стого однородного гиперграфа, которая обеспечивает наличие справедливой раскраски в два цвета.
Справедливые раскраски, простые гиперграфы
Короткий адрес: https://sciup.org/142214996
IDR: 142214996
Список литературы О справедливых раскрасках простых гиперграфов
- Hajnal A., Szemer´edi E. Proof of a conjecture of P. Erd˝os//Combinatorial theory and its applications, II (Proc. Colloq., Balatonfu¨red, 1969). 1970. P. 601-623.
- Erd˝os P., Lova´sz L. Problems and results on 3-chromatic hypergraphs and some related questions//Infnite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai. 1973. V. 10. P. 609-627.
- Lu L., Sz´ekely L. Using Lov´asz Local Lemma in the space of random injections//Electronic Journal of Combinatorics. 2007. V. 13. Research paper N 63.
- Shabanov D.A. Equitable two-colorings of uniform hypergraphs//European Journal of Combinatorics. 2015. V. 43. P. 185-203.
- Kozik J., Shabanov D.A. Improved algorithms for colorings of simple hypergraphs and applications//Journal of Combinatorial Theory, Series B. 2016. V. 116. 312-332.
- Kostochka A.V., R¨odl V. Constructions of sparse uniform hypergraphs with high chromatic number//Random Structures and Algorithms. 2010. V. 36, N 1. P. 46-56.
Статья научная
