Consider a triangle-free graph $G$, in which the vertices are partitioned in blocks $V = A_1 \sqcup \dots \sqcup A_k$.

$G$ has the property that, for each $i \leq j$, each vertex in $A_i$ has at most $d 2^{i-j}$ neighbors in $A_j$.

What can be said about the chromatic number $\chi(G)$?

It is simple to see that $\chi(G) \leq O(d)$ (simply color all the vertices in $A_k$ in a greedy manner, than all the vertices in $A_{k-1}$, etc.)

I can show that $\chi(G) \leq O(\frac{d \log \log d}{\log d})$, as follows. Let $s = \log \log d$. Partition the vertices into groups $B_i = A_i \cup A_{s+i} \cup A_{2s + i} \cup \dots$ for $i = 1, \dots, s$.

We now claim $\chi(B_i) \leq O( \frac{d}{\log d})$. To see that this is true, we suppose that each vertex has an available color palette of size $c \frac{d}{\log d}$ where $c$ is a sufficiently large constant.

Start at the largest value $j s+i$, and color $G[A_{j s + i}]$ using $O(d/\log d)$ colors (it has degree $d$ and is triangle free.) Now look at the graph $G[A_{(j-1) s + i}]$. Each vertex touches at most $d 2^{-s} = d/\log d$ already-colored vertices. So it has at least $\Omega(\frac{d}{\log d})$ colors remaining in its palette. So it can be list-colored.

Continue this process to color $A_{(j-1) s + i}, A_{(j-2) s + i}, \dots, A_i$.

Is this bound tight? Can you obtain $\chi(G) \leq O( \frac{d}{\log d})$? (the factor of $\log \log d$ seems weird to me)