|
Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)
Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами
А. Б. Купавский Московский физико-технический институт (государственный университет)
Аннотация:
Изучаются дистанционные графы с экспоненциально большим хроматическим числом, не содержащие $k$-клик, т. е. полных подграфов размера $k$. Явные конструкции графов строятся на основе векторов целочисленной решетки. Для большого класса графов получены точные оценки параметров, при выполнении которых эти графы не содержат $k$-клик. За счет этого улучшены оценки снизу максимума хроматических чисел графов
описанного класса. Приведен новый вероятностный подход для построения дистанционных графов без $k$-клик,
который дает лучшие оценки максимума хроматических чисел при больших $k$.
Библиография: 23 наименования.
Ключевые слова:
дистанционный граф, хроматическое число, кликовое число, задача Нельсона.
Поступило в редакцию: 08.02.2012 Исправленный вариант: 12.07.2012
Образец цитирования:
А. Б. Купавский, “Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами”, Изв. РАН. Сер. матем., 78:1 (2014), 65–98; Izv. Math., 78:1 (2014), 59–89
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/im7962https://doi.org/10.4213/im7962 https://www.mathnet.ru/rus/im/v78/i1/p65
|
Статистика просмотров: |
Страница аннотации: | 512 | PDF русской версии: | 193 | PDF английской версии: | 15 | Список литературы: | 62 | Первая страница: | 30 |
|