<p>Determining the classical Ramsey number <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(R(K_5)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>5</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and its variants is notoriously challenging. Even the simplest weakened Ramsey number <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq4.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">\(R_2^3(K_5)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>R</mi> <mn>2</mn> <mn>3</mn> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>5</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> remains unknown, and despite recent breakthroughs by Magnant and Schiermeyer (J Graph Theory 101:455–492, 2022), the Gallai–Ramsey number <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">\(gr_k(K_5)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <msub> <mi>r</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>5</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is still unresolved. The weakened Gallai–Ramsey number <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(gr_s^t(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <msubsup> <mi>r</mi> <mi>s</mi> <mi>t</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> bridges these two areas. Specifically, a graph <i>H</i> is said to satisfy <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq7.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="TEX">\(H \xrightarrow {(s,t)} G\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mover> <mo stretchy="false">→</mo> <mrow> <mo stretchy="false">(</mo> <mi>s</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mover> <mi>G</mi> </mrow> </math></EquationSource> </InlineEquation> if every <i>t</i>-edge-coloring of <i>H</i>, where each triangle uses at most two colors, forces a subgraph <i>G</i> with its edges colored in at most <i>s</i> colors. The number <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(gr_s^t(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <msubsup> <mi>r</mi> <mi>s</mi> <mi>t</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is defined as the smallest <i>n</i> such that the complete graph <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> has this property, while the weakened size Gallai–Ramsey number <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq10.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(sgr_s^t(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>g</mi> <msubsup> <mi>r</mi> <mi>s</mi> <mi>t</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the minimum number of edges in a graph <i>H</i> with <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq7.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="TEX">\(H \xrightarrow {(s,t)} G\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mover> <mo stretchy="false">→</mo> <mrow> <mo stretchy="false">(</mo> <mi>s</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mover> <mi>G</mi> </mrow> </math></EquationSource> </InlineEquation>. Budden and Wimbish (Australas J Combin 84:375–387, 2022) conjectured that <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq12.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="121" /> </InlineMediaObject> <EquationSource Format="TEX">\(gr_2^t(K_5)=2^t+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <msubsup> <mi>r</mi> <mn>2</mn> <mi>t</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>5</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mi>t</mi> </msup> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq13.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(t\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, which was fully resolved by Li, Broersma, and Wang (J Graph Theory 101:242–264, 2022). We establish its weakened size counterpart, proving that for <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_IEq14.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(t\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, <Equation ID="Equ3"> <MediaObject> <ImageObject Color="BlackWhite" FileRef="41980_2025_1009_Article_Equ3.gif" Format="GIF" Height="43" Rendition="HTML" Resolution="72" Type="Linedraw" Width="171" /> </MediaObject> <EquationSource Format="TEX">\(\begin{aligned} sgr_2^t(K_5)=\left( {\begin{array}{c}2^t+1\\ 2\end{array}}\right) . \end{aligned}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <mi>s</mi> <mi>g</mi> <msubsup> <mi>r</mi> <mn>2</mn> <mi>t</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>5</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <msup> <mn>2</mn> <mi>t</mi> </msup> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mn>2</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mo>.</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation></p>

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

Weakened Size Gallai–Ramsey Numbers for \(K_5\)

  • Ze Wang,
  • Yanbo Zhang

摘要

Determining the classical Ramsey number \(R(K_5)\) R ( K 5 ) and its variants is notoriously challenging. Even the simplest weakened Ramsey number \(R_2^3(K_5)\) R 2 3 ( K 5 ) remains unknown, and despite recent breakthroughs by Magnant and Schiermeyer (J Graph Theory 101:455–492, 2022), the Gallai–Ramsey number \(gr_k(K_5)\) g r k ( K 5 ) is still unresolved. The weakened Gallai–Ramsey number \(gr_s^t(G)\) g r s t ( G ) bridges these two areas. Specifically, a graph H is said to satisfy \(H \xrightarrow {(s,t)} G\) H ( s , t ) G if every t-edge-coloring of H, where each triangle uses at most two colors, forces a subgraph G with its edges colored in at most s colors. The number \(gr_s^t(G)\) g r s t ( G ) is defined as the smallest n such that the complete graph \(K_n\) K n has this property, while the weakened size Gallai–Ramsey number \(sgr_s^t(G)\) s g r s t ( G ) is the minimum number of edges in a graph H with \(H \xrightarrow {(s,t)} G\) H ( s , t ) G . Budden and Wimbish (Australas J Combin 84:375–387, 2022) conjectured that \(gr_2^t(K_5)=2^t+1\) g r 2 t ( K 5 ) = 2 t + 1 for \(t\ge 3\) t 3 , which was fully resolved by Li, Broersma, and Wang (J Graph Theory 101:242–264, 2022). We establish its weakened size counterpart, proving that for \(t\ge 2\) t 2 , \(\begin{aligned} sgr_2^t(K_5)=\left( {\begin{array}{c}2^t+1\\ 2\end{array}}\right) . \end{aligned}\) s g r 2 t ( K 5 ) = 2 t + 1 2 .