Chromatic tiling complexity and the chromatic number conjecture

Question

Let $T$ be a finite set of tiles in $\mathbb{R}^d$. A tiling of $\mathbb{R}^d$ by $T$ is a collection of disjoint translates of tiles in $T$ whose union is $\mathbb{R}^d$. A tiling is $k$-chromatic if its tiles can be colored with $k$ colors such that no two tiles sharing a $(d-1)$-dimensional face have the same color. The chromatic tiling complexity $\chi_T(d)$ is the smallest $k$ such that every tiling by $T$ is $k$-chromatic.

Let $G$ be the graph with vertices corresponding to tiles in $T$, with edges between tiles that can share a $(d-1)$-dimensional face in a tiling.

Is it true that $\chi_T(d) \leq \chi(G)$.

I suspect the conjecture holds, but strict inequality might arise from intricate tile shapes or specific tiling patterns that force long-range color dependencies not captured by the adjacency graph.

Answer 1

It can be strict already for $d=2$. Let $T$ consist of five tiles: a square, and four very silly shapes that nevertheless can be put together such that they pairwise share a $1$-dimensional face (thereby forming a $K_4$). Make the other sides of these four shapes so that nothing else can fit to them. This way the only tilings by $T$ can only use squares, so $\chi_T(2)=3$.

ps. And I recommend using the notation $\chi(T)$ instead of $\chi_T(d)$.