given the graph defined in this post: A binary sequence graph
i.e., Define a graph $H(n,2)$ as follows. Each vertex corresponds to a length nn binary sequence and two vertices are adjacent if and only if they differ in exactly two positions.
how would one go about finding its chromatic number?
Each sequence of length $n-1$ needs its own color and the last (parity) bit can be ignored, so: $$\chi(H_n) = 2^{n-1}$$
Enumerate the strings and colors and find that any sequence $X10Y$ has an edge in common with $X01Y$, similar for $X11Y$ and $X00Y$. This requires a new color.
The final bit does not need a new color.