2015/10/16 by Christopher Cox, Michael Ferrara, Cox, Christopher +5
Computer Science · Mathematics · #05C #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1510.04843
openalex publication_date 2015/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A sequence of nonnegative integers \π =(d1,d2,...,dn) is graphic if\nthere is a (simple) graph G of order n having degree sequence \π. In\nthis case, G is said to realize or be a realization of \π. Given a graph\nH, a graphic sequence \π is potentially H-graphic if there is some\nrealization of \π that contains H as a subgraph.\n In this paper, we consider a degree sequence analogue to classical graph\nRamsey numbers. For graphs H1 and H2, the potential-Ramsey number\nrpot(H1,H2) is the minimum integer N such that for any N-term\ngraphic sequence \π, either \π is potentially H1-graphic or the\ncomplementary sequence \\π=(N-1-dN,\…, N-1-d1) is potentially\nH2-graphic.\n We prove that if s\≥ 2 is an integer and Tt is a tree of order t>\n7(s-2), then rpot(Ks, Tt) = t+s-2. This result, which is best\npossible up to the bound on t, is a degree sequence analogue to a classical\n1977 result of Chv 'atal on the graph Ramsey number of trees vs. cliques. To\nobtain this theorem, we prove a sharp condition that ensures an arbitrary graph\npacks with a forest, which is likely to be of independent interest.\n