|
Записки научных семинаров ПОМИ, 2022, том 518, страницы 192–200
(Mi znsl7298)
|
|
|
|
О хроматических числах графов типа Джонсона
Д. Д. Черкашин С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, наб. р. Фонтанки 27, 191023, С.-Петербург, Россия
Аннотация:
Графом типа Джонсона $J_\pm(n,k,t)$ назовем граф, вершинами которого являются вектора из множества $\{0,\pm 1\}^n$ длины $\sqrt{k}$, а ребра проведены между парами векторов со скалярным произведением $t$. В работе найден порядок роста хроматических чисел графов $J_\pm(n,2,-1)$ и $J_\pm(n,3,-1)$ (логарифмический по $n$), а также $J_\pm(n,3,-2)$ (повторно-логарифмический по $n$). Библ. – 4 назв.
Ключевые слова:
дистанционные графы, раскраски графов, теорема Шпернера.
Поступило: 22.02.2022
Образец цитирования:
Д. Д. Черкашин, “О хроматических числах графов типа Джонсона”, Комбинаторика и теория графов. XIII, Зап. научн. сем. ПОМИ, 518, ПОМИ, СПб., 2022, 192–200
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl7298 https://www.mathnet.ru/rus/znsl/v518/p192
|
|