The chromatic number of the union of two graphs

Question

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$?

Answer 1

This is a comment, not an answer, but it will be more convenient to post it as an answer. Consider the vertices of $G_n$ as subsets of $[n]=\{1,\dots,n\}$.

Observation 1. $\chi(G_n)\ge\left\lfloor\frac{3n}2\right\rfloor+1$.

This is because $G_n$ contains a clique of that size, namely,
$\varnothing,\{1\},\{2\},\{1,2\},\{1,2,3\},\{1,2,4\},\{1,2,3,4,\},\{1,2,3,4,5\},\dots$.

Observation 2. The OP noted that $\chi(G_n)\le\binom{n+1}2+1=\frac{n^2+n+2}2$. For odd $n$ this bound can be improved to $\chi(G_n)\le\frac{n^2+3}2$.

The vertices $\varnothing$ and $[n]$ get their own colors. If $1\le|X|\le n-1$, color $X$ with the ordered pair $$\left(\sum_{x\in X}x\mod(n+1),\ \left\lceil\frac{|X|}2\right\rceil\right).$$ This is a proper coloring, so (assuming $n$ is odd) $$\chi(G_n)\le2+(n+1)\cdot\frac{n-1}2=\frac{n^2+3}2.$$

Observation 3. The clique number $\omega(G_n)$ is exactly $\left\lfloor\frac{3n}2\right\rfloor+1$.

We showed in Observation 1 that $\omega(G_n)\ge\left\lfloor\frac{3n}2\right\rfloor+1$. Let us prove by induction that $\omega(G_n)\le\left\lfloor\frac{3n}2\right\rfloor+1$.

We may assume $n\ge2$. Let $\mathcal C$ be a maximal clique in $G_n$. Let $\mathcal C_h=\{X\in\mathcal C:|X|=h\}$. Choose $h$ so that $0\lt h\lt n$ and $\mathcal C_h\ne\varnothing$.

If $\bigcup\mathcal C_h=[n]$ and $\bigcap\mathcal C_h=\varnothing$, then $|\mathcal C|=|\mathcal C_h|+2\le n+2\le\left\lfloor\frac{3n}2\right\rfloor+1$. Otherwise, choose $X\in\{\bigcup\mathcal C_h,\ \bigcap\mathcal C_h\}$ so that $0\lt|X|\lt n$, and let $k=|X|$. Then every element of $\mathcal C$ is a subset or superset of $X$. Since $0\lt k\lt n$, by induction we have $$|\mathcal C|\le\omega(G_k)+\omega(G_{n-k})-1\le\left\lfloor\frac{3k}2\right\rfloor+\left\lfloor\frac{3(n-k)}2\right\rfloor+1\le\left\lfloor\frac{3n}2\right\rfloor+1.$$

Answer 2

In a similar vein to $\chi^{\ast}(G_n)$, we can define a quantity $\chi^{\ast \ast}(G_n)$ as follows: Suppose you have an abelian group $M$ and a set $S=\{x_1, x_2, \dots, x_n\}\subset M$, such that for every non-empty subset $T\subset \{1,2,\dots,n\}$ we have $$\sum_{i\in T}x_i\neq 0.$$ Then you can color the graph $G_n$ by assigning the color $\sum_{i\in T}x_i$ to the vertex corresponding to $T$. It is not difficult to check that this gives a proper coloring of $G_n$ and that it satisfies the extra condition in the definition of $\chi^{\ast}$. Then we define $\chi^{\ast \ast}(G_n)$ as the smallest amount of colors used in such a coloring as we go over all choices of $S$ and $M$. Thus we have the following bounds $$\chi(G_n)\le \chi^{\ast}(G_n)\le \chi^{\ast\ast}(G_n).$$

The quantity $\chi^{\ast \ast}(G_n)$ was originally studied in the paper

R. B. Eggleton, P. Erdős, "Two combinatorial problems in group theory" Acta Arith. 21 (1972), 111-116

where it was shown that $\chi^{\ast \ast}(G_n)\le\lceil\frac{n^2}{2}\rceil+1$. They make the conjecture that this is always equality but this was later shown to be false already for $n=7$. They also conjectured that an optimal coloring among abelian groups can always be achieved using a cyclic group.

As far as lower bounds, Olson showed that $\chi^{\ast \ast}(G_n)\geq \frac{n^2}{9}$ in the paper

J. E. Olson, "Sums of sets of group elements", Acta Arith. 28 (1975), 147–156

and I believe that the best known bound is $\chi^{\ast \ast}(G_n)\geq \frac{n^2}{6}$ from

W. Gao, M. Huang, W. Hui, Y. Li, C. Liu, J. Peng, "Sums of sets of abelian group elements", J. Number Theory, 208 (2020), 208–229

In the end, this is all to say that if one were able to show a lower bound of $\left(\frac{1}{4}+o(1)\right)n^2$ for $\chi(G_n)$ or $\chi^{\ast}(G_n)$ this would significantly improve what is known about $\chi^{\ast\ast}(G_n)$, so it seems like this can be filed under "open problem" for the time being.