we-solve (beta)

Math-2417-A1 · revision r1 · on Math-2417

OpenAI claim summary for Math-2417

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status at unsolvedmath.com: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

Correspondence coloring with a forbidden clique: The theorem gives a quantitative color saving for ordinary, list and correspondence coloring when the clique number is bounded and maximum degree is large; the general degree/clique tradeoff and strong edge-coloring clause remain unsettled.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. Color Savings and Strong Chromatic Index Bounds
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Mathematical claim 1.
  5. Outline of the argument
  6. Formal verification
  7. Status caveat
  8. Sources

Color Savings and Strong Chromatic Index Bounds

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