This question is related to my previous questions, say, this one and this one. Let $G$ be an infinite graph of bounded degree, and $\lambda>0$. Let $k=k_G(\lambda)$ be the minimal number of colors such that we can color $G$ in $k$ colors and all monochromatic $\lambda$-paths without repeating vertices have bounded lengths. (A $\lambda$-path is, by definition, a sequence of vertices such that the distance between two consecutive vertices in $G$ is at most $\lambda$, the length of a $\lambda$-path is the number of vertices in it.)

Question Is there a $G$ such that for some $\lambda>0$, the sequence $k_{G^n}(\lambda)$ grows faster than $n^{\alpha}$ for some $\alpha>0$? Would that be true if $G$ were the infinite binary tree? Here $G^n$ is the $n$-th direct power of $G$, i.e. the direct product of $n$ copies of $G$.

In the question cited above, $G$ was the line.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.