Worked solution: Kang–Kelly–Kühn–Methuku–Osthus asymptotic proof via iterative absorption (2021)

Step 4 of 8: Shaving off the extra

+1

: handling near-complete graphs

Previous step Next step

In plain words

To drop the warm-up bound from $n+1$ to $n$ , the leftover graph handed to Vizing's theorem needs maximum degree one smaller -- which fails only when almost every vertex has full degree $n-1$ in size- $2$ edges, i.e. when the hypergraph $\mathcal{H}$ looks almost like the complete graph $K_n$ .

So the authors split into two cases: if $\mathcal{H}$ is not close to $K_n$ , the nibble-and-absorption argument can be tightened to save that one degree; if $\mathcal{H}$ is close to $K_n$ , they switch to deep $1$ -factorisation theorems tailored specifically for near-complete graphs.

\Delta(\mathcal{H}\setminus\mathcal{H}') \le n - 1 - |C|

Detailed analysis

Kang, Kelly, Kühn, Methuku and Osthus (2023, Section 2.1, Definition 2.2) formalise "close to $K_n$ " via the notion of a $(\rho,\varepsilon)\text{-full}$ hypergraph: one where almost all vertices have size- $2$ degree at least $(1-\varepsilon)n$ and a noticeable fraction have the maximum possible degree $n-1$ .

When $\mathcal{H}$ is not $(\rho,\varepsilon)\text{-full}$ , the nibble-and-absorption construction can be refined so that any uncovered "defect" vertices of the matchings fall inside $S := \{u \in U : d_G(u) < n-1\}$ , which lowers the leftover degree bound by one to $\Delta(\mathcal{H}\setminus\mathcal{H}') \le n - 1 - |C|$ , and Vizing's theorem then gives $\chi'(\mathcal{H}) \le n$ directly. When $\mathcal{H}$ is $(\rho,\varepsilon)\text{-full}$ , the authors instead apply the overfull-subgraph and $1$ -factorisation machinery developed by Csaba, Kühn, Lo, Osthus and Treglown to decompose the dense size- $2$ core directly.

Terms in this step

$(\rho,\varepsilon)\text{-full}$ hypergraph: An $n$ -vertex linear hypergraph whose size- $2$ edges alone make it look almost like $K_n$ : at least $(1-10\varepsilon)n$ vertices have size- $2$ degree at least $(1-\varepsilon)n$ , and at least $(\rho-15\varepsilon)n$ vertices have the full degree $n-1$ .

Knowledge used in this step

Graph coloring and the four color theorem