Ramsey for complete graphs with dropped cliques

Jonathan Chappelon, Luis Pedro Montejano, Jorge Luis Ramírez Alfonsín

Published 2013-07-24, updated 2014-12-12Version 3

Let $K\_{[k,t]}$ be the complete graph on $k$ vertices from which a set of edges, induced by a clique of order $t$, has been dropped. In this note we give two explicit upper bounds for $R(K\_{[k\_1,t\_1]},\dots, K\_{[k\_r,t\_r]})$ (the smallest integer $n$ such that for any $r$-edge coloring of $K\_n$ there always occurs a monochromatic $K\_{[k\_i,t\_i]}$ for some $i$). Our first upper bound contains a classical one in the case when $k\_1=\cdots =k\_r$ and $t\_i=1$ for all $i$. The second one is obtained by introducing a new edge coloring called {\em $\chi\_r$-colorings}. We finally discuss a conjecture claiming, in particular, that our second upper bound improves the classical one in infinitely many cases.