The classification of critical graphs and star-critical Ramsey numbers.

摘要

The graph Ramsey number R(G,H) is the smallest integer n such that every 2-coloring of the edges of Kn contains either a red copy of G or a blue copy of H. This implies that there exists a critical graph, a 2-coloring of Kn -1 that does not contain a red copy of G or a blue copy of H. These facts propose a question. What is the largest star K1,k that can be removed from Kn so that the underlying graph is still forced to have either a red copy of G or a blue copy of H? That is, determine the smallest integer k such that every 2-coloring of Kn - K1,n-2- k has either a red G or a blue H and there exists a 2-coloring of Kn - K1,n-2- k without a red G or a blue H. We have determined this integer for various classes of graphs G and H where R(G,H) is known. In addition to finding star-critical Ramsey numbers, we have also classified the critical graphs for various graph Ramsey numbers.