Generalizing the Ramsey problem through diameter

Dhruv Mubayi

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

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.

Détail

DOI : 10.37236/1658

Classification : 05C55, 05C15, 05C35
Mots-clés : generalised Ramsey number, diameter, biaprtite graph, complete graph