RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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.

UDC: 519.174.7, 519.174.3, 519.157.4

Received: 22.02.2022



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024