A391721 Restricted size Ramsey numbers r*(P_3, C_n).

8, 6, 9, 9, 13, 15, 17, 18, 20, 22

Offset

3,1

Comments

Size Ramsey number r_e(G,H) is the smallest number of edges in a graph F such that under any 2-coloring of its edges F contains either a red copy of G or a blue copy of H.

Restricted size Ramsey number requires additionally that F be a spanning subgraph of K_r, where r=r(G,H) is the Ramsey number of G and H.

Links

Table of n, a(n) for n=3..12.

Joanna Cyman and Tomasz Dzido, Restricted size Ramsey number for P_3 versus cycles, arXiv:1706.08134 [math.CO], 2017-2018.

Denny Riama Silaban, Edy Tri Baskoro, and Saladin Uttunggadewa, On The Restricted Size Ramsey Number, Proc. Comp. Sci., Vol. 74, 2015, Pages 21-26.

Formula

a(n) <= 2n - 1 (Silaban, Baskoro & Uttungadewa).

a(n) <= 2n - 2 for even n>=12 (Cyman & Dzido).

Cyman and Dzido conjecture that a(n) = 2n - 2 for all n>=10.

Crossrefs

Sequence in context: A249103 A382005 A116517 * A302517 A326285 A104668

Adjacent sequences: A391718 A391719 A391720 * A391722 A391723 A391724

Keyword

nonn,hard,more

Author

Elijah Beregovsky, Dec 18 2025

Status

approved