"Записки научных семинаров ПОМИ"
Том 518, стр. 192-200
О хроматических числах графов типа Джонсона
Д. Д. Черкашин
С.-Петербургское отделение Математического института им. В. А. Стеклова РАН,
наб. р. Фонтанки 27, 191023 С.-Петербург, Россия
jiocb.orlangyr@gmail.com
- Аннотация:
Графом типа Джонсона $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 назв.
- Ключевые слова: дистанционные графы, раскраски графов, теорема Шпернера
[distance graphs, graph colorings, Sperner theorem]
Полный текст(.pdf)