8
$\begingroup$

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.

$\endgroup$

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.