Chvátal-type results for degree sequence Ramsey numbers

الأصل · EN

A sequence of nonnegative integers π=(d₁,d₂,...,dₙ) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realize or be a realization of π. Given a graph H, a graphic sequence π is potentially H-graphic if there is some realization of π that contains H as a subgraph. In this paper, we consider a degree sequence analogue to classical graph Ramsey numbers. For graphs H₁ and H₂, the potential-Ramsey number rpot(H₁,H₂) is the minimum integer N such that for any N-term graphic sequence π, either π is potentially H₁-graphic or the complementary sequence π=(N-1-dₙ,, N-1-d₁) is potentially H₂-graphic. We prove that if s≥ 2 is an integer and Tₜ is a tree of order t> 7(s-2), then rpot(Kₛ, Tₜ) = t+s-2. This result, which is best possible up to the bound on t, is a degree sequence analogue to a classical 1977 result of Chvátal on the graph Ramsey number of trees vs. cliques. To obtain this theorem, we prove a sharp condition that ensures an arbitrary graph packs with a forest, which is likely to be of independent interest.