Description
Absztrakt:
A coloring is called $s$-wide if no walk of length $2s-1$ connects
vertices of the same color. A graph is $s$-widely colorable with $t$
colors if and only if it admits a homomorphism into a universal graph
$W(s,t)$. Tardif observed that the value of the $r^{\rm th}$
multichromatic number $\chi_r(W(s,t))$ of these graphs is at least
$t+2(r-1)$ and equality holds for $r=s=2$. He asked whether there is
equality also for $r=s=3$. We show that $\chi_s(W(s,t))=t+2(s-1)$ for
all $s$ thereby answering Tardif's question. We observe that for large
$r$ (with respect to $s$ and $t$ fixed) we cannot have equality and that
for $s$ fixed and $t$ going to infinity the fractional chromatic number
of $W(s,t)$ also tends to infinity. The latter is a simple consequence
of another result of Tardif on the fractional chromatic number of
generalized Mycielski graphs.
Társszerző Simonyi Gábor.
Zoom link: https://zoom.us/j/2961946869