Search

Correspondence coloring with a fixed forbidden subgraph

Networks with no fixed-size clique have larger independent sets and need fewer colors, by a log factor.

2 papers September 25, 2026 Explained by AI

An independent set is a group of points in a network with no links between them. If no four points are all linked, such sets should be larger than in general networks. One paper proves they are larger by a factor of order log d, where d is the average number of links. A second paper claims a matching saving in colors, even for a harder kind of coloring.

First step
1981
Ajtai, Erdős, Komlós and Szemerédi, who posed the independence conjecture
Significance
Major
It settles two long-standing conjectures on independent sets and coloring in clique-free graphs.
Trust
Formal proof listed
Field
Combinatorics
2 papers

The explanation

Draw five points in a ring, each joined to its two neighbors. Pick points so that no two picked points are joined. Such a choice is an independent set. In the ring of five, you can pick two points, but never three. Now draw six points as two separate triangles. Again you can pick only two, one from each triangle.

A simple rule says how many you can always pick. Say there are n points with d links each on average. Then you can always pick at least n divided by d + 1. Groups of points that are all joined to each other, called cliques, show the rule cannot be improved in general. The two triangles fit it exactly: 6 divided by 3 is 2.

What if the network has no large clique? Suppose no four points are all joined to each other. Then much larger independent sets should exist. For triangle-free networks, Ajtai, Komlós and Szemerédi showed this in 1980. The gain is a factor of about log d, the natural logarithm of the average number of links. For a million points with 1,000 links each on average, the simple rule promises about 999 points. A bound of n log d divided by d would give about 6,908.

In 1981, Ajtai, Erdős, Komlós and Szemerédi conjectured the same gain when any fixed clique is banned. They proved a weaker gain, of order log log d. Shearer later came within a factor of log log d of the goal. A log log is tiny, about 1.9 when d is 1,000, but it grows without limit.

One paper proves the conjecture for every fixed clique size r of at least 4. Every network with no r points all joined has an independent set of at least a constant times n log d divided by d. The constant depends only on r. The order cannot be improved, even for triangle-free networks.

A second paper turns to coloring. Give each point a color so that joined points differ. If each point has at most Δ links, Δ + 1 colors always suffice. Color the points one at a time, avoiding colors their neighbors already use. Correspondence coloring is a harder version, introduced by Dvořák and Postle. Each point gets its own list of options, and each link says which options clash across it. Take a ring of four points with two options each. Ordinary coloring works by alternating. But let one link clash option 1 with option 2, and vice versa. Then no choice works, as a check of all 16 cases confirms. Any correspondence bound also covers ordinary coloring.

Without triangles, Johansson showed that about Δ divided by log Δ colors are enough. With a fixed clique banned, his bound kept an extra log log Δ factor. That was still the best general correspondence bound for r of at least 4. Dhawan, Janzer and Methuku had removed the extra factor for ordinary coloring in a narrower family of cases.

That paper claims a bound of order Δ divided by log Δ for every network with no r-point clique, once Δ is large. It applies to correspondence coloring, and so to ordinary coloring too. The same holds when any fixed network F is banned as a part. This settles a conjecture of Alon, Krivelevich and Sudakov in a stronger form. When F contains a closed loop, the order Δ divided by log Δ cannot be improved. Neither paper gives a value for its constants.

The main obstacle was triangles. Banning four-point cliques still allows many triangles, and triangles spoil the counting that works when they are absent. The independence proof spreads weights over the points. Its central step bounds the weight on triangles by a constant times the weight on links. The coloring proof colors a few points at a time in random rounds. Removing one option can knock out two clashing options at once, which creates unwanted correlations. It reuses and extends the triangle tools of the independence paper to pay for this.

How sure is this? A computer proof checker called Lean has checked a formal version of the independence bound. It covers every network with no r-point clique, for each r of at least 4, with average degree at least 2. The coloring paper is not in the Lean scope note, so its result remains a claim. The independence proof claims no efficient method for finding the sets. No specialist review of these papers has been published.

What it doesn't show. This does not give values for the constants, or claim a fast method for finding the independent sets.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if the proofs hold. Lean has checked a formal version of the independence bound. The coloring result is outside the Lean note, the constants have no stated value, and no specialist review is published.

Words used

Independent set
A group of points in a network with no link between any two of them.
Clique
A group of points that are all linked to each other.
Average degree
The average number of links at a point, written d.
Correspondence coloring
Coloring where each point has its own list of options and each link says which options clash across it.
Logarithm
A slowly growing function; the natural log of 1,000 is about 6.9.
Lean
A computer program that checks each step of a formally written proof.

The original papers (2)

Lean notes

All quoted lines (22)
  1. For general graphs, the elementary bound α(G)≥n/(d+1)\alpha(G)\ge n/(d+1) is best possible, as disjoint unions of cliques show.
    A logarithmic independence bound for clique-free graphs Back to text
  2. Ajtai, Koml\'os and Szemer\'edi proved the logarithmic improvement when triangles are excluded.
    A logarithmic independence bound for clique-free graphs Back to text
  3. They proved the lower bound Ωr(nlog⁡log⁡d/d)\Omega_r(n\log\log d/d) as d→∞d\to\infty, so excluding any fixed clique already improves on the general bound.
    A logarithmic independence bound for clique-free graphs Back to text
  4. Theorem … removes this remaining log⁡log⁡d\log\log d denominator.
    A logarithmic independence bound for clique-free graphs Back to text
  5. We prove that the improvement is a factor of order log⁡d\log d.
    A logarithmic independence bound for clique-free graphs Back to text
  6. The theorem gives a positive answer to the fixed-clique-size independence conjecture of Ajtai, Erd\Hos, Koml\'os and Szemer\'edi, also recorded as Erd\Hos Problem 802.
    A logarithmic independence bound for clique-free graphs Back to text
  7. The order nlog⁡d/dn\log d/d is best possible up to a constant factor even for triangle-free graphs, and hence for the larger class of KrK_r-free graphs.
    A logarithmic independence bound for clique-free graphs Back to text
  8. Thus χ(G)≤χlist(G)≤χDP(G)≤Δ(G)+1,\chi(G)\le \chi_{\mathrm{list}}(G)\le\chi_{\mathrm{DP}}(G) \le \Delta(G)+1, where the last inequality follows by greedy coloring.
    Correspondence coloring graphs with a forbidden clique Back to text
  9. Dvo\vr\'ak and Postle introduced correspondence coloring in their 2015 preprint, published as, to allow the identification of colors to vary from edge to edge.
    Correspondence coloring graphs with a forbidden clique Back to text
  10. This notion includes list coloring: replace each color in each list by a distinct copy, and match copies of the same color along an edge.
    Correspondence coloring graphs with a forbidden clique Back to text
  11. Johansson subsequently obtained the list-coloring bounds O(Δ/log⁡Δ)O(\Delta/\log\Delta) for triangle-free graphs and Or(Δlog⁡log⁡Δ/log⁡Δ)O_r(\Delta\log\log\Delta/\log\Delta) for KrK_r-free graphs.
    Correspondence coloring graphs with a forbidden clique Back to text
  12. In particular, the previous general upper bound for fixed r≥4r\ge4 was χDP(G)=Or ⁣(Δlog⁡log⁡Δlog⁡Δ).\chi_{\mathrm{DP}}(G) =O_r\!\left(\frac{\Delta\log\log\Delta}{\log\Delta}\right).
    Correspondence coloring graphs with a forbidden clique Back to text
  13. More recently, Dhawan, Janzer, and Methuku proved Ot(Δ/log⁡Δ)O_t(\Delta/\log\Delta) for ordinary coloring of Kt,t,tK_{t,t,t}-free graphs, and hence for every fixed three-colorable forbidden graph.
    Correspondence coloring graphs with a forbidden clique Back to text
  14. We prove a logarithmic improvement when the clique number is bounded.
    Correspondence coloring graphs with a forbidden clique Back to text
  15. The corollary therefore proves that conjecture in the stronger correspondence-coloring form.
    Correspondence coloring graphs with a forbidden clique Back to text
  16. If FF contains a cycle, the order Δ/log⁡Δ\Delta/\log\Delta cannot be improved in general: graphs with girth larger than ∣V(F)∣|V(F)| can have maximum degree at most Δ\Delta and chromatic number of this order; see also the proof of.
    Correspondence coloring graphs with a forbidden clique Back to text
  17. We do not optimize the constant or the degree threshold.
    Correspondence coloring graphs with a forbidden clique Back to text
  18. The central step is to show that TG(w)T_G(w) is at most a constant depending only on rr times MG(w)M_G(w) when ww maximizes, over nonnegative vertex weights, FG(w)=∑vwv(1−log⁡wv)−MG(w).F_G(w)=\sum_v w_v(1-\log w_v)-M_G(w).
    A logarithmic independence bound for clique-free graphs Back to text
  19. The proof constructs a partial coloring in small random rounds.
    Correspondence coloring graphs with a forbidden clique Back to text
  20. Even after compensating their individual losses to first order, this shared deletion creates a positive edge correlation.
    Correspondence coloring graphs with a forbidden clique Back to text
  21. The structural argument develops the multiplier and entropy-splitting methods of the companion manuscript A logarithmic independence bound for clique-free graphs.
    Correspondence coloring graphs with a forbidden clique Back to text
  22. The proof gives an existence result with an rr-dependent constant; it makes no claim of an efficient algorithm or an optimal leading constant.
    A logarithmic independence bound for clique-free graphs Back to text

Other sources

  1. M. Ajtai, J. Komlós and E. Szemerédi, “A note on Ramsey numbers”, Journal of Combinatorial Theory, Series A 29(3) (1980), 354–360
  2. M. Ajtai, P. Erdős, J. Komlós and E. Szemerédi, “On Turán’s theorem for sparse graphs”, Combinatorica 1(4) (1981), 313–317
  3. J. B. Shearer, “On the independence number of sparse graphs”, Random Structures & Algorithms 7(3) (1995), 269–271
  4. N. Alon, M. Krivelevich and B. Sudakov, “Coloring graphs with sparse neighborhoods”, Journal of Combinatorial Theory, Series B 77(1) (1999), 73–82
  5. Z. Dvořák and L. Postle, “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8”, Journal of Combinatorial Theory, Series B 129 (2018), 38–54
  6. A. Dhawan, O. Janzer and A. Methuku, “Independent sets and colorings of K_{t,t,t}-free graphs”, arXiv:2511.17191 (2025)
  7. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Combinatorics Erdős problemsGraph theoryOpen since the 1980sLean-checked results