Generalizing the Ramsey Problem through Diameter

Abstract

Given a graph $G$ and positive integers $d,k$, let $f_d^k(G)$ be the maximum $t$ such that every $k$-coloring of $E(G)$ yields a monochromatic subgraph with diameter at most $d$ on at least $t$ vertices. Determining $f_1^k(K_n)$ is equivalent to determining classical Ramsey numbers for multicolorings. Our results include $\bullet$ determining $f_d^k(K_{a,b})$ within 1 for all $d,k,a,b$ $\bullet$ for $d \ge 4$, $f_d^3(K_n)=\lceil n/2 \rceil +1$ or $\lceil n/2 \rceil$ depending on whether $n \equiv 2 (mod 4)$ or not $\bullet$ $f_3^k(K_n) > {{n}\over {k-1+1/k}}$ The third result is almost sharp, since a construction due to Calkin implies that $f_3^k(K_n) \le {{n}\over {k-1}} +k-1$ when $k-1$ is a prime power. The asymptotics for $f_d^k(K_n)$ remain open when $d=k=3$ and when $d\ge 3, k \ge 4$ are fixed.

Locations

• The Electronic Journal of Combinatorics - View - PDF