<p>Hadwiger conjectured in 1943 that for every integer <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$t \ge 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, every graph with no <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$K_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation>-minor is <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">$(t-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-colorable. Kostochka, and independently Thomason, proved every graph with no <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$K_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation>-minor is <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq5.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">$O(t(\log t)^{1/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>t</mi> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-colorable. Recently, Postle improved it to <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="104" /> </InlineMediaObject> <EquationSource Format="TEX">$O(t (\log \log t)^6)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>t</mi> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mo>log</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> <mn>6</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-colorable. In this paper, we show that every graph with no <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$K_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation>-minor is <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2899_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="104" /> </InlineMediaObject> <EquationSource Format="TEX">$O(t (\log \log t)^{5})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>t</mi> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mo>log</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> <mn>5</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-colorable.</p>

Improved Bound for Hadwiger’s Conjecture

期刊论文
发表日期：

2025年2月18日

查看全文

Yan Wang

摘要

Hadwiger conjectured in 1943 that for every integer $t \ge 1$ $t \geq 1$ , every graph with no $K_t$ $K_{t}$ -minor is $(t-1)$ $(t - 1)$ -colorable. Kostochka, and independently Thomason, proved every graph with no $K_t$ $K_{t}$ -minor is $O(t(\log t)^{1/2})$ $O (t {(log t)}^{1 / 2})$ -colorable. Recently, Postle improved it to $O(t (\log \log t)^6)$ $O (t {(log log t)}^{6})$ -colorable. In this paper, we show that every graph with no $K_t$ $K_{t}$ -minor is $O(t (\log \log t)^{5})$ $O (t {(log log t)}^{5})$ -colorable.