# The chromatic number of the union of two graphs

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

• @JoshuaZ: sure; color each vertex with the scalar product of the corresponding string and the vector $(1,2,\dotsc,n)$.
– Seva
Nov 20 at 16:36
• what do you mean by lying below? Nov 21 at 8:48
• @FedorPetrov: one of the corresponding subsets of the $n$-element set being contained in another one.
– Seva
Nov 21 at 9:03
• Here is a nice $17$-colouring of $G_7$ where I am using subsets of $\{0,1,\ldots,6\}$ to represent the vertices. Let $\sigma = (0,1,2,3,4,5,6)$ be a cyclic permutation and let $\tau$ be the complement map on the subsets. Let $F= \{013, 124, 235, 346, 450, 561, 602\}$ be the Fano plane and set $C = F \cup F^\tau$. Then take $D = \{0, 16, 25, 34, 124, 135, 236, 456\}$ and its seven rotations under powers of $\sigma$, and $D^\tau$ and its seven rotations under powers of $\sigma$. Then one colour class for each of $\emptyset$ and the entire set, making a total of 17 classes. Nov 22 at 7:04
• So $G_6$ has chromatic number $16$ - this took quite a long time to compute, almost all of which was spent searching in vain for a $15$-colouring. I think it will be hard to get close to an exact answer. Nov 23 at 2:29

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

• Some more computational snippets: the cliques you found are the unique maximum clique (up to equivalence under the automorphism group) for $G_4$, $G_6$ and $G_8$. For $G_5$, $G_7$ and $G_9$ there are other classes of equally-large cliques, but none larger. Nov 25 at 2:56
• So I liked your original proof that if $|\mathcal{C}_h| = 1$ for some $h$, then the result follows. Did you decide that it was not so obvious to prove that there must be a layer containing just one vertex of the clique? Nov 26 at 5:11