|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
О хроматических числах некоторых дистанционных графов
Д. А. Захаров Национальный исследовательский университет "Высшая школа экономики", г. Москва
Аннотация:
Для натуральных чисел $n > r > s$ определим граф $G(n,r,s)$:
вершинами этого графа являются $r$-элементные подмножества
$n$-элементного множества, пара множеств смежна, если их пересечение
содержит ровно $s$ элементов. В этой работе мы изучаем
хроматические числа этого семейства графов. В частности,
найдено точное значение хроматического числа $G(n,3,2)$
для бесконечно многих $n$. Также мы улучшаем
наилучшие известные верхние оценки хроматических чисел
для многих значений параметров $r$, $s$
и всех достаточно больших $n$.
Библиография: 21 название.
Ключевые слова:
хроматическое число, дистанционный граф, верхние оценки.
Поступило: 05.08.2016 Исправленный вариант: 30.08.2018
Образец цитирования:
Д. А. Захаров, “О хроматических числах некоторых дистанционных графов”, Матем. заметки, 107:2 (2020), 210–220; Math. Notes, 107:2 (2020), 238–246
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm11349https://doi.org/10.4213/mzm11349 https://www.mathnet.ru/rus/mzm/v107/i2/p210
|
Статистика просмотров: |
Страница аннотации: | 279 | PDF полного текста: | 30 | Список литературы: | 33 | Первая страница: | 15 |
|