A General Lower Bound on Gallai-Ramsey Numbers for Non-Bipartite Graphs

Abstract

Given a graph $H$ and a positive integer $k$, the $k$-color Gallai-Ramsey number $gr_{k}(K_{3} : H)$ is defined to be the minimum number of vertices $n$ for which any $k$-coloring of the complete graph $K_{n}$ contains either a rainbow triangle or a monochromatic copy of $H$. The behavior of these numbers is rather well understood when $H$ is bipartite but when $H$ is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs $H$ to a value that we conjecture to be sharp up to a constant multiple.

Keywords

• Gallai-Ramsey numbers
• edge-coloring
• graph Ramsey numbers