On the chromatic numbers of Johnson type graphs

2025/08/27 by Cherkashin, Danila
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.19775

Abstract

A Johnson type graph J_±(n,k,t) is a graph whose vertex set consists of vectors from \-1,0,1\ⁿ of the length √(k) and edges connect vertices with scalar product t. The paper determines the order of growth of the chromatic numbers of graphs J_±(n,2,-1) and J_±(n,3,-1) (logarithmic on n), and also J_±(n,3,-2) (double logarithmic on n).

Citations

• Independence numbers of Johnson-type graphs
• Intersection theorems for 0,\± 1 -vectors and\n s-cross-intersecting families

Related

• On the Chromatic Number of Grassmann Graphs
• Edge and mixed metric dimension of Johnson graphs
• On the b-chromatic number of the Cartesian product of two complete graphs
• The Chromatic Number of the q-Kneser Graph for q ≥ 5
• Independence numbers of Johnson-type graphs