Selmer M. Johnson worked on bounds for codes, both unrestricted codes
and constant weight codes. The *Johnson scheme* J(*n*,*m*)
named after him is the association scheme of which the elements are the
*m*-subsets of a *n*-set, and the relation (called
*Johnson distance*) of two *m*-sets is half the size of
their symmetric difference.

The Johnson graph J(*n*,*m*) is the graph that describes
the distance-1 relation in the Johnson scheme.
It is distance-regular of diameter min(*m*, *n* – *m*).
In particular, for *m* = 2 it is strongly regular,
and the parameters are
*v* = *m*(*m* – 1)/2,
*k* = 2(*m* – 2),
λ = *m* – 2,
μ = 4.

This graph J(*n*,2) is also known as the *triangular graph*
T(*n*). It can be regarded as the special case of the block graph
of a Steiner system for the trivial Steiner systems
S(2,2,*n*).
The first nontrivial case is T(5), the complement of the
Petersen graph. For *n* smaller than 4
these graphs are complete. The graph T(4) is the complete multipartite
graph K_{3×2}, the complement of 3K_{2}.

The triangular graphs T(*n*) are uniquely determined by their
parameters when *n* is not 8. The three
Chang graphs have the same parameters as T(8).

The complement of the triangular graph T(*n*) has (for *n*
at least 4) independence number *n*–1 and chromatic number
*n*–2.

More generally, the Kneser graph K(*n*,*m*) has (for *n*
at least 2*m*) independence number (*n*–1 choose *m*–1)
and chromatic number *n*–2*m*+2.

The independence number of the Johnson graph J(*n*,*m*) is
the size of the largest constant weight code with word length *n*,
weight *m*, and minimum distance 4. There is a lot of literature.
See, e.g., Brouwer et al. (1990).
The chromatic number of J(*n*,*m*) is the minimum number
of parts in a partition into such constant weight codes. One has
χ(J(*n*,*m*)) ≤ *n* (since one can put the structure
of abelian group on the coordinate positions, and all words with given
sum of the elements in the support form a constant weight code with
minimum distance 4). Often the chromatic number is a little bit smaller.
For example, since there is for *n* = 1,3 (mod 6), *n* > 7,
a partition of all triples into Steiner triple systems
STS(*n*),
it follows that χ(J(*n*,3)) = *n*–2 for these *n*.
A general lower bound is χ(J(*n*,*m*)) ≥ *n*–*m*+1.
See also Etzion & Bitan (1996) and Brouwer & Etzion (2009).

A table with bounds on the chromatic number of the Johnson graph
J(*n*,*m*):

n\m | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|---|

5 | 5 | 5 | |||||||

6 | 6 | 5 | 6 | ||||||

7 | 7 | 7 | 6 | ||||||

8 | 8 | 7 | 7 | 6 | |||||

9 | 9 | 9 | 7 | 8 | |||||

10 | 10 | 9 | 10 | 8--9 | 8 | ||||

11 | 11 | 11 | 10 | 10 | 8--9 | ||||

12 | 12 | 11 | 11 | 10--11 | 10--11 | 8--9 | |||

13 | 13 | 13 | 11 | 11--13 | 10--13 | 10--13 | |||

14 | 14 | 13 | 13 | 11--13 | 11--14 | 10--14 | 10--14 | ||

15 | 15 | 15 | 13 | 13--14 | 12--15 | 11--15 | 10--15 | ||

16 | 16 | 15 | 16 | 13--14 | 13--15 | 12--15 | 11--16 | 10--15 |

A.E. Brouwer, James B. Shearer, N.J.A. Sloane & Warren D. Smith,
*A new table of constant weight codes*,
IEEE Trans. Inform. Th. **36** (1990) 1334-1380.

Tuvi Etzion & Sara Bitan,
*On the chromatic number, colorings, and codes of the Johnson graph*,
Discr. Applied Math. **70** (1996) 163-175.

Luc Teirlinck,
*A completion of Lu's determination of the spectrum of
large sets of disjoint Steiner triple systems*,
J. Combin. Th. (A) **57** (1991) 302-305.

Lijun Ji,
*A new existence proof for large sets of disjoint Steiner triple systems*,
J. Combin. Th. (A) **112** (2005) 308-327.