For graphs G and H, the Ramsey number R(G, H) is the smallest r such that any red-blue edge coloring of <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1312_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">$K_r$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>r</mi> </msub> </math></EquationSource> </InlineEquation> contains a red G or a blue H. The path-critical Ramsey number <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1312_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">$R_{\pi }(G,H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mi>π</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the largest n such that any red-blue edge coloring of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1312_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$K_r \setminus P_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mi>r</mi> </msub> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> contains a red G or a blue H, where <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1312_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">$r=R(G,H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mi>R</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1312_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$P_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> is a path of order n. In this note, we show a general upper bound for <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1312_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">$R_{\pi }(G,H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mi>π</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and determine the exact values for some cases of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1312_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">$R_{\pi }(G,H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mi>π</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>.

On some path-critical Ramsey numbers

期刊论文
发表日期：

2025年5月25日

查看全文

Ye Wang,
Yanyan Song

摘要

For graphs G and H, the Ramsey number R(G, H) is the smallest r such that any red-blue edge coloring of $K_r$ $K_{r}$ contains a red G or a blue H. The path-critical Ramsey number $R_{\pi }(G,H)$ $R_{π} (G, H)$ is the largest n such that any red-blue edge coloring of $K_r \setminus P_{n}$ $K_{r} \ P_{n}$ contains a red G or a blue H, where $r=R(G,H)$ $r = R (G, H)$ and $P_{n}$ $P_{n}$ is a path of order n. In this note, we show a general upper bound for $R_{\pi }(G,H)$ $R_{π} (G, H)$ , and determine the exact values for some cases of $R_{\pi }(G,H)$ $R_{π} (G, H)$ .