Полноцветные справедливые раскраски простых однородных гиперграфов
Автор: Ширгазина И. Р.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 2 (54) т.14, 2022 года.
Бесплатный доступ
В статье изучается задача о полноцветных справедливых раскрасках простых однородных гиперграфов. Пусть H = (V, E) - гиперграф, раскраска в r цветов множества вершин V называется полноцветной, если в ней каждое ребро из E содержит вершины всех r цветов. Также раскраска множества вершин в r цветов называется полноцветной справедливой, если она полноцветная и мощности любых двух цветовых классов отличаются не более чем на один. Доказана новая оценка максимальной степени вершины, которая гарантирует существование полноцветной справедливой 3-раскраски в простом n-однородном гиперграфе.
Гиперграфы, раскраски гиперграфов, полноцветные раскраски, справедливые раскраски, вероятностный метод
Короткий адрес: https://sciup.org/142235305
IDR: 142235305
Список литературы Полноцветные справедливые раскраски простых однородных гиперграфов
- Hajnal A., Szemerédi Е. Proof of a conjecture of P. Erdôs // Combinatorial Theory and its Applications. London: North-Holland, 1970. P. 601-623.
- Erdos P., Lovasz L. Problems and results on 3-chromatic hvpergraphs and some related questions // Infinite and Finite Sets. — Colloquia Mathematica Societatis Janos Bolvai. 1973. V. 10. P. 609-627.
- Radhakrishnan J., Srinivasan A. Improved bounds and algorithms for hvpergraph two-coloring // Random Structures and Algorithms. 2000. V. 16. P. 4-32.
- Cherkashin D., Kozik J. A note on random greedy coloring of uniform hvpergraphs // Random Structures and Algorithms. 2015. V. 47. P. 407-413.
- Akolzin I.A., Shabanov D.A. Colorings of hvpergraphs with large number of colors // Discrete Mathematics. 2016. V. 339. P. 3020-3031.
- Lu L., Szekely L. Using Lovasz Local Lemma in the space of random injections // Electronic Journal of Combinatorics. 2007. V. 13. Research paper N 63.
- Kozik J., Shabanov D.A. Improved algorithms for colorings of simple hvpergraphs and applications // Journal of Combinatorial Theory, Series B. 2016. V. 116. P. 312-332.
- Акользип И.А. О справедливых раскрасках простых гиперграфов // Труды МФТИ. 2017. Т. 9, № 4. С. 161-173.
- Шабанов Д.А. Экстремальные задачи для раскрасок равномерных гиперграфов // Известия РАН Серия математическая. 2007. Т. 71, № 6. С. 183-222.
- Шабанов Д.А. О существовании полноцветных раскрасок для равномерных гиперграфов // Математический сборник. 2010. Т. 201, № 4. С. 137-160.
- Розовская А.П., Шабанов Д.А. Экстремальные задачи для полноцветных раскрасок равномерных гиперграфов // Дискретная математика. 2012. Т. 24, № 2. С. 104-122.
- Cherkashin D. A note on panchromatic colorings // Discrete Mathematics. 2018. V. 341. P. 652-657.
- Кравцов Д.А., Крохмалъ H.E., Шабанов Д.А. О полноцветной раскраске случайного гиперграфа // Успехи математических наук. 2018. Т. 73, № 4. С. 175-176.
- Кравцов Д.А., Крахмаль Н.Е., Шабанов Д.А. Полноцветные раскраски случайных гиперграфов // Дискретная математика. 2019. Т. 31, № 2. С. 84-113.
- Kravstov D., Krokhmal N., Shabanov D. Panchromatic 3-colorings of random hvpergraphs // European Journal of Combinatorics. 2019. V. 78. P. 28-43.
- Хузиева, А.Э. Случайные конструкции гиперграфов с большим обхватом, не допускающих полноцветных раскрасок // Фундамент, и прикл. матем. 2020. Т. 23, № 1. С. 269-283.
- Alon N., Spencer J. The Probabilistic Method. 4th edition. Wiley. Hoboken, 2016.
- Kozik J. Multipass greedy coloring of simple uniform hvpergraphs // Random Structures and Algorithms. 2015. V. 48. P. 125-146.
- Shabanov D.A. Equitable two-colorings of uniform hvpergraphs // European Journal of Combinatorics. 2015. V. 43. P. 185-203.
