Good Graph Hunting

Abstract

Given graphs $H_1,H_2,\dots ,H_k$, the Ramsey number $R(H_1,\dots ,H_k)$ is the smallest integer $n$ for which in any coloring of the edges of the complete graph $K_n$ with colors $1,2,\dots ,k$, there is some color $i$ with a monochromatic copy of $H_i$. We call a tuple $(H_1,\dots ,H_k)$ good if for every $k$-coloring of the edges of an $R(H_1,\dots ,H_k)$-chromatic graph, there is some color $i$ with a monochromatic copy of $H_i$. We call a graph $H$ $k$-good if the $k$-tuple $(H,H,\dots ,H)$ is good, and $H$ is good if it is $k$-good for every $k$. Bialostocki and Gyárfás proved that matchings are good and asked whether every acyclic $H$ is good. A natural strategy shows that $P_4$ is $k$-good for $k\ne 3$ and that $(P_4,P_5)$ is good. We develop a new technique for showing that a graph is $2$-good, and we apply it successfully to $P_5$, $P_6$, and $P_7$.

Cited by in corpus (1)

• Ramsey-nice families of graphs