Article ID Journal Published Year Pages File Type
5777659 Journal of Combinatorial Theory, Series B 2017 7 Pages PDF
Abstract
Given a pair of graphs G and H, the Ramsey number R(G,H) is the smallest N such that every red-blue coloring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If graph G is connected, it is well known and easy to show that R(G,H)≥(|G|−1)(χ(H)−1)+σ(H), where χ(H) is the chromatic number of H and σ the size of the smallest color class in a χ(H)-coloring of H. A graph G is called H-good if R(G,H)=(|G|−1)(χ(H)−1)+σ(H). The notion of Ramsey goodness was introduced by Burr and Erdős in 1983 and has been extensively studied since then. In this short note we prove that n-vertex path Pn is H-good for all n≥4|H|. This proves in a strong form a conjecture of Allen, Brightwell, and Skokan.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,