<p>For a graph <i>G</i> and a family of graphs <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(\cal{H}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">H</mi> </mrow> </math></EquationSource> </InlineEquation>, the <i>Ramsey number</i> <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\(r(G,\cal{H})\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>r</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mrow> <mi mathvariant="script">H</mi> </mrow> <mo class="MJX-tex-caligraphic" mathvariant="script" stretchy="false">)</mo> </math></EquationSource> </InlineEquation> is defined as the minimum integer <i>n</i> such that any red/blue edge-coloring of <i>K</i><sub><i>n</i></sub> contains either a red copy of <i>G</i> or a blue copy of some member in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(\cal{H}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">H</mi> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we determine the exact value of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq4.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\(r(\hat{K}_{n},\cal{L})\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>r</mi> <mo stretchy="false">(</mo> <msub> <mrow> <mover> <mi>K</mi> <mo stretchy="false">^</mo> </mover> </mrow> <mrow> <mi>n</mi> </mrow> </msub> <mo>,</mo> <mrow> <mi mathvariant="script">L</mi> </mrow> <mo class="MJX-tex-caligraphic" mathvariant="script" stretchy="false">)</mo> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq5.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(\hat{K}_{n}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mrow> <mover> <mi>K</mi> <mo stretchy="false">^</mo> </mover> </mrow> <mrow> <mi>n</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> is a kipas and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\cal{L}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">L</mi> </mrow> </math></EquationSource> </InlineEquation> is a set of linear forests with a given size. Using the result, we further determine the Gallai-Ramsey number <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq7.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="100" /> </InlineMediaObject> <EquationSource Format="TEX">\(\text{gr}_{3}(K_{1,3}:\hat{K}_{n})\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mtext>gr</mtext> <mrow> <mn>3</mn> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> <mo>:</mo> <msub> <mrow> <mover> <mi>K</mi> <mo stretchy="false">^</mo> </mover> </mrow> <mrow> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation>, which is the minimum integer <i>N</i> such that any 3-edge-colored <i>K</i><sub><i>N</i></sub> contains either a rainbow copy of <i>K</i><sub>1,3</sub> or a monochromatic copy of <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_52_Article_IEq5.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(\hat{K}_{n}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mrow> <mover> <mi>K</mi> <mo stretchy="false">^</mo> </mover> </mrow> <mrow> <mi>n</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Ramsey Numbers for Linear Forest-Kipas and Its Applications in Gallai-Ramsey Numbers

  • Ping Li,
  • Ya-ping Mao,
  • Ingo Schiermeyer,
  • Yi-fan Yao

摘要

For a graph G and a family of graphs \(\cal{H}\) H , the Ramsey number \(r(G,\cal{H})\) r ( G , H ) is defined as the minimum integer n such that any red/blue edge-coloring of Kn contains either a red copy of G or a blue copy of some member in \(\cal{H}\) H . In this paper, we determine the exact value of \(r(\hat{K}_{n},\cal{L})\) r ( K ^ n , L ) , where \(\hat{K}_{n}\) K ^ n is a kipas and \(\cal{L}\) L is a set of linear forests with a given size. Using the result, we further determine the Gallai-Ramsey number \(\text{gr}_{3}(K_{1,3}:\hat{K}_{n})\) gr 3 ( K 1 , 3 : K ^ n ) , which is the minimum integer N such that any 3-edge-colored KN contains either a rainbow copy of K1,3 or a monochromatic copy of \(\hat{K}_{n}\) K ^ n .