Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_184_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$r \ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> be fixed and G be an n-vertex graph. A long-standing conjecture of Győri states that if <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_184_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="138" /> </InlineMediaObject> <EquationSource Format="TEX">$e(G) = t_{r-1}(n) + k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi>t</mi> <mrow> <mi>r</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_184_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$t_{r-1}(n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>t</mi> <mrow> <mi>r</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denotes the number of edges of the Turán graph on n vertices and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_184_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$r - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> parts, then G has at least <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_184_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="98" /> </InlineMediaObject> <EquationSource Format="TEX">$(2 - o(1))k/r$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>-</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mi>k</mi> <mo stretchy="false">/</mo> <mi>r</mi> </mrow> </math></EquationSource> </InlineEquation> edge disjoint r-cliques. We prove this conjecture.

Packing edge disjoint cliques in graphs

期刊论文
出版模式：

开放获取
发表日期：

2025年10月14日

查看全文

József Balogh,
Michael C. Wigal

摘要

Let $r \ge 3$ $r \geq 3$ be fixed and G be an n-vertex graph. A long-standing conjecture of Győri states that if $e(G) = t_{r-1}(n) + k$ $e (G) = t_{r - 1} (n) + k$ , where $t_{r-1}(n)$ $t_{r - 1} (n)$ denotes the number of edges of the Turán graph on n vertices and $r - 1$ $r - 1$ parts, then G has at least $(2 - o(1))k/r$ $(2 - o (1)) k / r$ edge disjoint r-cliques. We prove this conjecture.