On the chromatic numbers of Johnson type graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908505891405824 |
|---|---|
| author | Cherkashin, Danila |
| author_facet | Cherkashin, Danila |
| contents | 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$). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19775 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the chromatic numbers of Johnson type graphs Cherkashin, Danila Combinatorics 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$). |
| title | On the chromatic numbers of Johnson type graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.19775 |