On the chromatic number, colorings, and codes of the Johnson graph Original Research Article

We consider the Johnson graph J(n, w), 0 ⩽ w ⩽ n. The graph has (nw) vertices representing the (nw) w-subsets of an n-set. Two vertices are connected by an edge if the intersection between their w-subsets is a (w − 1)-set. Let θ(n, w) be the chromatic number of this graph. It is well known that θ(n, w) ⩽ n. We give some constructions which yield θ(n, w) < n for some cases of n and w. The colorings associated with the chromatic number and other colorings of the graph lead to improvements on the lower bounds on the sizes of some constant weight codes.