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

Матем. сб., 2013, том 204, номер 4, страницы 49–78 (Mi sm7830)

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

Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера

Е. Е. Демёхинa, А. М. Райгородскийab, О. И. Рубановab

a Механико-математический факультет Московского государственного университета им. М. В. Ломоносова
b Факультет инноваций и высоких технологий Московского физико-технического института

Аннотация: Доказано существование последовательностей дистанционных графов $G_n\subset\mathbb R^n$, хроматические числа которых растут экспоненциально, но которые в то же время не содержат клик или циклов заданного наперед размера.
Библиография: 42 названия.

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

УДК: 519.112.4+519.174+519.176

MSC: 05C15, 05C35, 05D10

Поступила в редакцию: 14.12.2010 и 09.12.2011

DOI: 10.4213/sm7830


 Англоязычная версия: Sbornik: Mathematics, 2013, 204:4, 508–538

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


© МИАН, 2024