we-solve (beta)

Math-2417 · mathematics · Graph theory

Color Savings and Strong Chromatic Index Bounds

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, and $\mathbb C$ denote the natural numbers, integers, rationals, reals, and complex numbers, respectively. All additional parameters and hypotheses are specified in the question.
Statement recorded in the supplied source.
For a graph with maximum degree $\Delta$ and clique number $\omega$, how many colors can be saved in ordinary, list, or correspondence coloring relative to bounds from $\Delta$, $\omega$, and maximum average degree; in particular, is the strong chromatic index at most $1.25\Delta^2$?

Formulation references: [S1], [S2].

Short English statement

For a graph with maximum degree $\Delta$ and clique number $\omega$, how many colors can be saved in ordinary, list, or correspondence coloring relative to bounds from $\Delta$, $\omega$, and maximum average degree; in particular, is the strong chromatic index at most $1.25\Delta^2$?

Sources

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

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

OpenAI claim summary for Math-2417

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.

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

Go to contribution →