we-solve (beta)

Math-2602 · mathematics · Combinatorics

Logarithmic correspondence-coloring bound for fixed forbidden cliques

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
For each fixed $r>=4$, do constants $C_r,Delta_r$ exist such that every finite $K_r-subgraph-free$ graph of maximum degree $Delta>=Delta_r$ has correspondence chromatic number at most $ceil(C_r$ Delta/log Delta)?

Short English statement

For each fixed $r>=4$, do constants $C_r,Delta_r$ exist such that every finite $K_r-subgraph-free$ graph of maximum degree $Delta>=Delta_r$ has correspondence chromatic number at most $ceil(C_r$ Delta/log Delta)?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-2602-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-2602

For each fixed $r\ge4$, the selected paper asserts the displayed correspondence-coloring bound for $K_r$-free graphs when maximum degree exceeds a threshold depending on $r$. Its constants depend only on that forbidden-clique size, exactly as required by this question. The same manuscript also states a version with a fixed forbidden graph.

Logarithmic correspondence-coloring bound for fixed forbidden cliques

OpenAI's claim

Correspondence coloring with a forbidden clique: For each fixed $r\ge4$, the paper claims correspondence chromatic number $O_r(\Delta/\log\Delta)$ in graphs with no $K_r$ subgraph and large maximum degree. Ordinary and list-coloring versions follow, and fixed forbidden subgraphs are also covered.

Mathematical statement of the claimed result

Mathematical claim 1.
For every fixed integer $r\ge4$ there are $C_r>0,\Delta_r\ge3$ with the following implication for a finite simple undirected graph $G$, writing $\Delta=\Delta(G)$: if $\Delta\ge\Delta_r$ and no $K_r$ occurs, then \[\chi_{\mathrm{DP}}(G)\le\left\lceil C_r\frac\Delta{\log\Delta}\right\rceil.\] The DP, or correspondence, chromatic number permits a matching of forbidden color pairs across each edge rather than identical color names. The stated corollary replaces $K_r$-freeness by noninduced $F$-freeness for any fixed finite graph $F$, with constants depending on $F$. It does not prescribe the optimal leading constant or strong edge-coloring bounds.

Outline of the argument

Correspondence coloring with a forbidden clique: Random partial-coloring rounds act directly on the graph of available list entries and forbidden matching pairs. Weights track total list supply, individual probabilities, and conflicting edge mass. An entropy-and-mass potential pays for losses when neighboring vertices are colored, including local adjustments for triangles, until the residual lists can be completed.

Formal verification

Family 184 describes Lean coverage for a large independent set in a fixed-clique-free graph at the logarithmically improved scale; correspondence coloring is separate.

Correspondence coloring with a forbidden clique: No manuscript-specific Comparator is listed in the pinned inventory.

The documented selection does not cover the entire manuscript assertion relevant here.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →