Справедливые раскраски гиперграфов с ограниченными степенями вершин
Автор: Ширгазина И. Р.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 2 (58) т.15, 2023 года.
Бесплатный доступ
В статье изучается задача о справедливых раскрасках однородных гиперграфов с ограничением на максимальную степень вершины. Пусть H = (V, Е) - гиперграф, раскраска в r цветов множества вершин V называется справедливой, если в ней каждое ребро из E не является одноцветным, а также мощности любых двух цветовых классов отличаются не более чем на единицу. В данной работе получено улучшение оценки максимальной степени вершины k-однородного гиперграфа, гарантирующей наличие справедливой раскраски в r > 2 цветов при достаточно большом числе вершин.
Гиперграфы, раскраски гиперграфов, справедливые раскраски, вероятностный метод
Короткий адрес: https://sciup.org/142238159
IDR: 142238159
Список литературы Справедливые раскраски гиперграфов с ограниченными степенями вершин
- Hajnal A., Szemer´edi E. Proof of a conjecture of P. Erd˝os // Combinatorial Theory and its Applications. North-Holland, London. 1970. P. 601–623.
- Erd˝os P., Lov´asz L. Problems and results on 3-chromatic hypergraphs and some related questions // Infinite and Finite Sets. — Colloquia Mathematica Societatis Janos Bolyai. 1973. V. 10. P. 609–627.
- Radhakrishnan J., Srinivasan A. Improved bounds and algorithms for hypergraph twocoloring // Random Structures and Algorithms. 2000. V. 16. P. 4–32.
- Pluh´ar A. Greedy colorings for uniform hypergraphs // Random Structures and Algorithms. 2009. V. 35. P. 216–221.
- Kostochka A.V., Kumbhat M., R¨odl V. Coloring uniform hypergraphs with small edge degrees // Fete of Combinatorics and Computer Science. — Bolyai Society Mathematical Studies. 2010. V. 20. P. 213–238.
- Shabanov D.A. On 𝑟-chromatic hypergraphs // Discrete Mathematics. 2012. V. 312. P. 441–458.
- Cherkashin D., Kozik J. A note on random greedy coloring of uniform hypergraphs // Random Structures and Algorithms. 2015. V. 47. P. 407–416.
- Akolzin I.A., Shabanov D.A. Colorings of hypergraphs with large number of colors // Discrete Mathematics. 2016. V. 339. P. 3020–3031.
- 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.
- Акользин И.А. О справедливых раскрасках простых гиперграфов // Труды МФТИ. 2017. Т. 9, № 4. С. 161–173.
- Ширгазина И.Р. Полноцветные справедливые раскраски простых однородных гиперграфов // Труды МФТИ. 2022. Т. 14, № 2. С. 169–188.
- Akhmejanova M., Shabanov D. A. Equitable colorings of hypergraphs with r colors // Journal of Mathematical Sciences volume. 2022. V. 262. P. 391–405.
- Akhmejanova M. B., Shabanov D. A. Equitable colorings of hypergraphs with few edges // Discrete Applied Mathematics. 2020. V. 276. P. 2–12.
- Alon N., Spencer J. The Probabilistic Method. 4th edition. Wiley. Hoboken, 2016.
- Kozik J. Multipass greedy coloring of simple uniform hypergraphs // Random Structures and Algorithms. 2015. V. 48. P. 125–146.
