Correspondence coloring with a fixed forbidden subgraph

1 · The essentials

Think of a graph as a collection of points joined by links, with a limit on how many links can meet at any point. The manuscripts ask how forbidding a fixed pattern of links affects the number of colors needed to color the points. The main manuscript shows that, when this limit is sufficiently large, forbidding any fixed pattern allows a color bound smaller than the limit by a logarithmic factor. This holds even for a more demanding coloring rule in which each link can specify which pairs of color choices conflict. A companion manuscript establishes a related guarantee: if a graph has no group of a fixed size whose points are all linked to one another, it contains a large collection of mutually unlinked points. The companion's result has a Lean formalization; the supplied source does not identify a formalization of the coloring result.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine assigning time slots to people, with links recording pairs whose assignments can conflict. Correspondence coloring lets each linked pair have its own table of incompatible slot choices, rather than simply forbidding them from choosing the same slot. The result says that excluding a fixed link pattern still gives a strong bound on how many choices suffice, subject to the stated size conditions.

Why it matters

The main manuscript describes its coloring result as resolving the Alon–Krivelevich–Sudakov conjecture in the stronger correspondence-coloring form. It also gives the same bounds for ordinary and list coloring. The Lean-formalized companion establishes the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.

2 · Going further

The coloring problem is to bound the correspondence chromatic number using the maximum degree $Δ$ when a fixed subgraph is forbidden. For every fixed integer $r \geq 4$ , the main manuscript shows that a $K_{r}$ -free graph of sufficiently large maximum degree has correspondence chromatic number $O_{r} (Δ/ lo g Δ)$ . Here $K_{r}$ denotes a group of $r$ vertices with every pair joined, and the subscript on $O_{r}$ allows the bound's constant to depend on $r$ .

The manuscript also states the bound $O_{F} (Δ/ lo g Δ)$ when any fixed graph $F$ is excluded as an ordinary subgraph. The dependence on $F$ matters: this is a guarantee for each fixed forbidden graph, not a stated uniform bound over all choices of $F$ . Ordinary coloring and list coloring satisfy the same bounds, while the correspondence-coloring statement is the stronger form highlighted by the source.

The companion addresses independent sets rather than color assignments. For every fixed integer $r \geq 4$ , every $K_{r}$ -free graph with $n$ vertices and average degree $d \geq 2$ has an independent set of size at least $c_{r} n lo g d / d$ , where $c_{r} > 0$ depends only on $r$ . This is the result identified as Lean-formalized. Both manuscripts concern the effect of excluding a fixed clique, but the supplied abstracts give no argument outline and do not specify how the independence result is used in the coloring manuscript.

Useful notions

Graphs, vertices, and edges
Maximum degree and average degree
Cliques and forbidden subgraphs
Coloring and independent sets
Logarithms and asymptotic bounds

What was known before / what is new

Before

The source identifies the Alon–Krivelevich–Sudakov coloring conjecture and the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi as the questions being resolved. It does not describe earlier bounds, partial results, or the history of either conjecture.

New

The main manuscript shows the logarithmically improved coloring bound in the stronger correspondence-coloring setting, including exclusion of any fixed graph as an ordinary subgraph. The companion establishes the lower bound $c_{r} n lo g d / d$ for independent sets under the fixed-clique-size hypotheses. That independence result has a Lean formalization.

Limits and assumptions

The clique statements require a fixed integer $r \geq 4$ . The coloring bound requires sufficiently large maximum degree, and its constants may depend on the forbidden clique or fixed graph $F$ ; exclusion of $F$ is as an ordinary subgraph. The independence bound requires average degree $d \geq 2$ , with a positive constant depending only on $r$ . The explicitly identified Lean formalization covers the independence result in Manuscript 2, not an explicitly stated formalization of the coloring claims in Manuscript 1. The supplied abstracts do not give proof methods or identify remaining open questions.

Mini glossary

Correspondence coloring: A coloring framework in which each edge specifies which pairs of choices at its endpoints are incompatible.
Maximum degree: The largest number of edges meeting any one vertex.
Average degree: The average, over all vertices, of the number of edges meeting a vertex.
Clique: A set of vertices in which every pair is joined by an edge.
Independent set: A set of vertices with no edges joining any pair of them.
Forbidden ordinary subgraph: A graph pattern that cannot be found by selecting vertices and edges of the graph under study.

Keywords : Correspondence coloring · Forbidden subgraphs · Independent sets

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Proves the Alon–Krivelevich–Sudakov coloring conjecture in correspondence-coloring form: graphs avoiding any fixed subgraph F need $O_{F} (Δ/ lo g Δ)$ colors when their maximum degree Δ is sufficiently large. Also proves the Ajtai–Erdős–Komlós–Szemerédi independence conjecture: for fixed r ≥ 4, every n-vertex K_r-free graph of average degree d ≥ 2 has an independent set of size $Ω_{r} (n lo g d / d)$ .

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/184.md

Manuscripts in this family

★

Correspondence coloring graphs with a forbidden clique

05/10/2026

To be verified

For every fixed integer r ≥ 4, we prove that every K_r-free graph of sufficiently large maximum degree Δ has correspondence chromatic number $O_{r} (Δ/ lo g Δ)$ . This resolves the Alon–Krivelevich–Sudakov coloring conjecture in the stronger correspondence-coloring form. The same bound, with a constant depending on F, holds when any fixed graph F is excluded as an ordinary subgraph. Ordinary and list coloring satisfy the same bounds.

PDF GitHub folder

A logarithmic independence bound for clique-free graphs

25/09/2026

Verified by Lean

For every fixed integer r ≥ 4, every K_r-free graph on n vertices with average degree d ≥ 2 has an independent set of size at least $c_{r} n lo g d / d$ , where $c_{r} > 0$ depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.

PDF GitHub folder Lean formalization