О числе Рамсея $R(K_{1,s},P_t)$

Х. Х. Абдуллин^a, Д. Б. Мокеев^ba, Д. С. Талецкий<sup>a

a</sup> Национальный исследовательский университет – Высшая школа экономики в Нижнем Новгороде
^b Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского

Аннотация: Числом Рамсея $R(K_{1,s},P_t)$ называется наименьшее натуральное число $n$ такое, что для любого $n$-вершинного графа $G$ верно следующее: либо $G$ содержит вершину степени не менее $s$, либо дополнение $G$ содержит простой $t$-путь. В этой статье найдены точные значения величины $R(K_{1,s},P_t)$ при некоторых значениях $s > t$.
Библиография: 18 названий.

Ключевые слова: число Рамсея, путь, звезда.

УДК: 519.154+519.174

MSC: 05D10

Поступило: 09.04.2025
Исправленный вариант: 18.06.2025

DOI: 10.4213/mzm14702