Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus, for instance, $G_2=K_4$, and $G_3$ has $25$ edges. What is the chromatic number of $G_n$?

There is a simple, but not quite obvious construction showing that $\chi(G_n)\le n(n+1)/2+1$, and I am interested in a matching lower bound. Computations give $$ \chi(G_1)=2,\ \chi(G_2)=4,\ \chi(G_3)=5,\ \chi(G_4)=9, $$ $$ \chi(G_5)=12,\ \chi(G_6)=16,\ \text{and}\ \chi(G_7)\le 17. $$ (The first five values are easy to compute, the last two are reported by Gordon Royle in the comments.)

*An update.* The colorings I am interesting in are of a special nature: if the strings $s$ and $t$ are same-colored, then (identifying strings with sets) also $s\setminus t$ and $t\setminus s$ are same-colored. Let $\chi^*(G)$ denote the smallest number of colors needed to properly color the graph $G$ in this special way. Is it true that $\chi^*(G_n)=(1/2+o(1))n^2$? That, say, $\chi^*(G_n)>(1/4+o(1))n^2$?

10more comments