A full logarithmic gain from excluding a fixed clique

← All digests

Family 184 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A graph with maximum degree $\Delta$ can always be colored with $\Delta+1$ colors by a greedy procedure. But if the graph contains no large clique, can substantially fewer colors suffice?

Forbidding a triangle is known to save a logarithmic factor. The longstanding question is whether forbidding any fixed clique gives the same order of improvement. A parallel question asks whether every clique-free graph has an independent set larger by a logarithmic factor than the elementary average-degree guarantee.

The two manuscripts claim both conclusions. M1 obtains $O_r(\Delta/\log\Delta)$ even for correspondence coloring, a generalization of list coloring with edge-specific conflicts. M2 obtains independent sets of size $\Omega_r(n\log d/d)$, where $d$ is average degree. Both remove an iterated-logarithm loss from the earlier general bounds.

2. Background and essential definitions

A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number $\chi(G)$ is the smallest palette size allowing this. An independent set contains no adjacent pair, and $\alpha(G)$ denotes its maximum size.

A clique $K_r$ is a set of $r$ pairwise adjacent vertices. A graph is $K_r$-free when it has no such set. The parameter $r$ will be fixed, while graph size and degree may grow.

The maximum degree is $\Delta$, the largest number of neighbors of any vertex. The average degree is

$$d=\frac{2|E(G)|}{n},$$

where $n$ is the number of vertices. These parameters can be very different when a few vertices have many more neighbors than the rest.

In list coloring, each vertex has its own set of allowed colors. A coloring must select an allowed color at every vertex and still avoid equal colors on adjacent vertices. The list chromatic number is the smallest list size that guarantees this for every assignment.

Correspondence coloring goes further. Give each vertex a separate list $L(v)$. For every edge $uv$, specify a matching between entries of $L(u)$ and entries of $L(v)$; matched pairs are forbidden together. The identifications may be inconsistent around a cycle. A valid coloring chooses one entry per list while avoiding every forbidden pair.

The correspondence chromatic number, also called the DP-chromatic number, is written $\chi_{\mathrm{DP}}(G)$. The basic hierarchy is

$$\chi(G)\leq\chi_{\mathrm{list}}(G) \leq\chi_{\mathrm{DP}}(G)\leq\Delta+1.$$

Ordinary and list coloring are special cases of correspondence coloring. All logarithms below are natural.

3. Development history and previous partial results

Ajtai, Komlós and Szemerédi proved a logarithmic improvement for independent sets in triangle-free graphs. Shearer sharpened this to asymptotic leading coefficient one:

$$\alpha(G)\geq(1-o(1))\frac{n\log d}{d}$$

as the average degree grows. Ajtai, Erdős, Komlós and Szemerédi conjectured in 1981 that the same order holds when any fixed clique is excluded. Their first general bound gained a factor $\log\log d$; Shearer later obtained a gain $\log d/\log\log d$.

The coloring story developed in parallel. Kim obtained the sharp asymptotic list-coloring order for graphs with no cycles of length three or four. Johansson proved $O(\Delta/\log\Delta)$ for triangle-free list coloring and

$$O_r\!\left(\frac{\Delta\log\log\Delta}{\log\Delta}\right)$$

for a general fixed forbidden clique. Molloy sharpened the triangle-free leading constant and gave a new proof of the clique-free estimate.

Dvořák and Postle introduced correspondence coloring, allowing colors to be identified differently across different edges. Bernshteyn extended the triangle-free and clique-free bounds to that stronger setting. The iterated-logarithm factor remained for general fixed cliques.

Other structural restrictions allowed sharper conclusions. Local sparsity in neighborhoods, bounded neighborhood coloring parameters, and particular forbidden subgraphs all supplied logarithmic gains. Davies, Kang, Pirot and Sereni developed a common framework using local occupancy of random independent sets.

More recently, Dhawan, Janzer and Methuku obtained the sharper ordinary-coloring order and leading-coefficient-one independence bounds when a fixed three-colorable graph is forbidden. That does not include every $K_r$-free graph for $r\geq4$. M1 and M2 claim to remove the remaining iterated-logarithm losses for the full fixed-clique setting.

4. What the new manuscripts claim

M1: correspondence coloring

For every fixed integer $r\geq4$, M1 states that constants $C_r$ and $\Delta_r$ exist such that every $K_r$-free graph with maximum degree $\Delta\geq\Delta_r$ satisfies

$$\chi_{\mathrm{DP}}(G) \leq\left\lceil C_r\frac{\Delta}{\log\Delta}\right\rceil.$$

The constants depend only on $r$, not on the number of vertices, the individual lists or the chosen matchings. Ordinary and list coloring inherit the same bound.

The paper deduces a result for every fixed forbidden graph $F$, where exclusion means ordinary subgraph exclusion, not induced exclusion. Taking $r\geq\max\{4,|V(F)|\}$, a $K_r$ contains $F$, so an $F$-free graph is $K_r$-free. Consequently,

$$\chi_{\mathrm{DP}}(G)=O_F(\Delta/\log\Delta).$$

The manuscript identifies the ordinary-coloring version as the Alon–Krivelevich–Sudakov conjecture. When $F$ contains a cycle, the order is optimal up to a constant in general, by high-girth examples with large chromatic number. It is not claimed to be sharp for every acyclic forbidden graph.

M2: independence in terms of average degree

For each fixed $r\geq4$, M2 claims a constant $c_r>0$ such that every $K_r$-free graph with $n$ vertices and average degree $d\geq2$ satisfies

$$\alpha(G)\geq c_r\frac{n\log d}{d}.$$

This resolves the fixed-clique-size independence conjecture stated above, according to the manuscript. The order is optimal up to constants even in the smaller class of triangle-free graphs.

The average-degree formulation is important: it uses the graph’s actual mean density, not an exceptional high-degree vertex. M2 does not optimize $c_r$. Neither manuscript claims the triangle-free leading coefficient one for every fixed clique size.

5. Why the advance matters

Importance: 4/5. The family establishes the full logarithmic improvement predicted by two major conjectures, including a coloring framework stronger than ordinary or list coloring.

Clique exclusion is a comparatively weak structural assumption. Neighborhoods may still contain many edges and triangles, and a graph can have high chromatic number despite having no fixed large clique. The bounds quantify exactly how much improvement this local prohibition forces at the level of general asymptotic order.

The two results are related but not interchangeable. A coloring contains a large independent color class, yet a maximum-degree coloring theorem does not immediately give the strongest average-degree statement. Conversely, repeatedly removing large independent sets does not automatically preserve a sharp correspondence-coloring bound. The companion methods address both the structural independence problem and the additional consistency issues of local color lists.

6. The main idea

Choose weights that reveal useful structure

M2 assigns nonnegative weights $w_v$ to vertices and maximizes an entropy-minus-edge expression:

$$F_G(w)=\sum_v w_v(1-\log w_v) -\sum_{uv\in E(G)}w_uw_v.$$

The convention $0\log0=0$ makes the expression continuous. The first term rewards spread-out positive weights; the second penalizes placing much weight on adjacent vertices.

At a maximizing weight, local variations relate a vertex’s weight to the total weight in its neighborhood. Clique exclusion permits additional random weight modifications, producing a bound on weighted edge mass between arbitrary vertex sets.

The key structural theorem then bounds weighted triangle mass by a constant multiple of weighted edge mass. It is designed to survive edge deletion and splitting a vertex into several copies, so the later reductions need not keep the weights at an optimizer.

Split neighborhoods while retaining triangle information

Random walks inside neighborhoods compare probability distributions started at different vertices. An entropy estimate controls how much these distributions change on average over triangles.

Coupling close distributions tends to group the two edges of a triangle together. Splitting a vertex according to these groups reduces the total neighbor weight seen by each copy while losing only a controlled amount of triangle mass. Iterating reaches bounded neighborhood weights, where the triangle-to-edge comparison becomes direct.

To extract an independent set, choose a vertex and delete its closed neighborhood, meaning the vertex together with all its neighbors. The weighted triangle bound controls the drop in the potential. Repeating this selection produces an independent set with the required logarithmic gain. Removing the original graph’s highest-degree vertices first converts a maximum-degree intermediate result into the stated average-degree theorem.

Extend the control to correspondence lists

M1 forms a new graph whose vertices are list entries and whose edges are forbidden pairs. Each list is an independent part. Because each edge correspondence is a matching, an entry has at most one neighbor in any other list. A clique in this conflict graph projects to a clique in the original graph, so clique exclusion survives.

The algorithmic-style argument colors in small random rounds, with nonnegative weights on available entries. Activations select entries while deleting their conflicts. Shared neighbors create correlations: one activation can remove both endpoints of a conflict edge, and the resulting cost is measured by weighted triangles.

A local adjustment lemma, developed from M2’s multiplier and splitting ideas, offsets that triangle cost. It also bounds how many entries from any one list an operation can affect. This extra participation control is necessary for concentration; a small graph-radius operation could otherwise touch many entries from one list.

Concentration estimates and the local lemma make the desired inequalities hold simultaneously across vertices. The rounds reduce remaining degrees faster than the available-list supply, after which a final coloring step completes the assignment.

7. Scope, limitations, and open questions

The forbidden clique size is fixed. The constants and degree thresholds may deteriorate with $r$; these are not uniform estimates for growing clique size.

M1 uses maximum degree and sufficiently large $\Delta$. M2 uses average degree $d\geq2$. Exchanging those parameters without an additional argument would change the statements.

For the general forbidden-graph corollary, containment is ordinary, not induced. Induced exclusion can permit large complete graphs and therefore cannot be substituted into the same conclusion.

The optimal leading constants are not determined, and the manuscripts do not supply optimized efficient algorithms for arbitrary input graphs or correspondence assignments. Their headline contribution is the sharp order of the logarithmic gain.

M2 also distinguishes its degree-sensitive statement from the off-diagonal Ramsey exponents in family 170. Those companion Ramsey results are cited for context and are not inputs to its proof. A bound on extremal graph order and a guarantee based on each graph’s average degree answer different quantitative questions.

8. Sources and further reading

M1 is the October 5 correspondence-coloring manuscript. M2 develops the weighted independence method and its average-degree consequence. Their introductions separately trace coloring and independent-set bounds.

Primary recent background includes Davies–Kang–Pirot–Sereni’s local-occupancy framework, Dhawan–Janzer–Methuku on three-colorable forbidden graphs, and Davies’s weighted local independence methods. The source bibliographies identify the original Ajtai–Erdős–Komlós–Szemerédi conjecture, Shearer’s independence bounds, Johansson’s coloring results and the correspondence-coloring extensions.

Source manuscripts

• M1. OpenAI, Correspondence coloring graphs with a forbidden clique (October 5, 2026).
• M2. OpenAI, A logarithmic independence bound for clique-free graphs (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.