Good Graph Hunting

Original · EN

Given graphs H₁, H₂,, Hₖ, the Ramsey number R(H₁,, Hₖ) is the smallest integer n for which in any coloring of the edges of the complete graph Kₙ with colors 1,2,,k, there is some color i with a monochromatic copy of Hᵢ. We call a tuple (H₁,, Hₖ) good if for every k-coloring of the edges of an R(H₁,, Hₖ)-chromatic graph, there is some color i with a monochromatic copy of Hᵢ. We call a graph H k-good if the k-tuple (H, H,, 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₄ is k-good for k = 3 and that (P₄, P₅) is good. We develop a new technique for showing that a graph is 2-good, and we apply it successfully to P₅, P₆, and P₇.