|
Zapiski Nauchnykh Seminarov POMI, 2022, Volume 518, Pages 192–200
(Mi znsl7298)
|
|
|
|
On the chromatic numbers of Johnson-type graphs
D. D. Cherkashin St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences
Abstract:
A Johnson type graph $J_{\pm}(n,k,t)$ is a graph whose vertex set consists of vectors from $\{-1,0,1\}^n$ of the length $\sqrt{k}$ and edges connect vertices with scalar product $t$. The paper determines the order of growth of the chromatic numbers of graphs $J_\pm(n,2,-1)$ and $J_\pm(n,3,-1)$ (logarithmic on $n$), and also $J_\pm(n,3,-2)$ (double logarithmic on $n$).
Key words and phrases:
distance graphs, graph colorings, Sperner theorem.
Received: 22.02.2022
Citation:
D. D. Cherkashin, “On the chromatic numbers of Johnson-type graphs”, Combinatorics and graph theory. Part XIII, Zap. Nauchn. Sem. POMI, 518, POMI, St. Petersburg, 2022, 192–200
Linking options:
https://www.mathnet.ru/eng/znsl7298 https://www.mathnet.ru/eng/znsl/v518/p192
|
Statistics & downloads: |
Abstract page: | 68 | Full-text PDF : | 28 | References: | 21 |
|