King Graph Ramsey Numbers

Abstract

A king graph $K{G}_n$ has $n^2$ vertices corresponding to the $n^2$ squares of an $n\times n$ chessboard. From one square (vertex) there are edges to all squares (vertices) being attacked by a king. For given graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest $n$ such that any 2-coloring of the edges of $K{G}_n$ contains $G$ in the first or $H$ in the second color. Results on existence and nonexistence of $r(G,H)$ and some exact values are presented.