RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2020, том 107, выпуск 2, страницы 210–220 (Mi mzm11349)

Эта публикация цитируется в 2 статьях

О хроматических числах некоторых дистанционных графов

Д. А. Захаров

Национальный исследовательский университет "Высшая школа экономики", г. Москва

Аннотация: Для натуральных чисел $n > r > s$ определим граф $G(n,r,s)$: вершинами этого графа являются $r$-элементные подмножества $n$-элементного множества, пара множеств смежна, если их пересечение содержит ровно $s$ элементов. В этой работе мы изучаем хроматические числа этого семейства графов. В частности, найдено точное значение хроматического числа $G(n,3,2)$ для бесконечно многих $n$. Также мы улучшаем наилучшие известные верхние оценки хроматических чисел для многих значений параметров $r$$s$ и всех достаточно больших $n$.
Библиография: 21 название.

Ключевые слова: хроматическое число, дистанционный граф, верхние оценки.

УДК: 519.17

Поступило: 05.08.2016
Исправленный вариант: 30.08.2018

DOI: 10.4213/mzm11349


 Англоязычная версия: Mathematical Notes, 2020, 107:2, 238–246

Реферативные базы данных:


© МИАН, 2024