Erdős problem #628 — wave 6g report

Access/research date: 2026-07-27 (UTC)

Claim labels used throughout:

• (a) elementary-rigorous — proved below from definitions.
• (b) rigorous-modulo-named-theorem — depends on the explicitly cited theorem.
• (c) plausible/structural-unverified — heuristic, estimate, or negative literature-search evidence.
• (d) computational-only — exact output of the supplied finite computation, subject to its stated trust boundary.

0. Mandatory live-page gate

(d: direct live-page observation) I fetched erdosproblems.com/628 and its discussion thread through the Bright Data browser route on 2026-07-27. This was a rendered live-page fetch, not the stale tracker YAML or a datacenter curl.

Verbatim statement

The following is the live rendered statement, with only its line wrapping normalized:

> Let 𝐺 be a graph with chromatic number 𝑘 containing no 𝐾𝑘. If 𝑎,𝑏 ≥2 and 𝑎 +𝑏 =𝑘 +1 then must there exist two disjoint subgraphs of 𝐺 with chromatic numbers ≥𝑎 and ≥𝑏 respectively?

(d: direct live-page observation) The page displays the badge FALSIFIABLE, an explicit open-status notice, 0 claimed proofs for this problem, Interested in collaborating: None, and Currently working on this problem: None. The other markers are: likes by Dogmachine and LaiC; “looks difficult,” “looks tractable,” “results could be formalisable,” and “working on formalising” are all None; “Formalised statement?” is No. The page says it was last edited 06 December 2025. Thus none of the mandatory stop conditions fired.

(d: direct live-page observation) The page itself lists:

• Erdős originally asked the \(a=b=3\) case, proved by Brown and Jung, in the stronger form of two vertex-disjoint odd cycles.
• Balogh–Kostochka–Prince–Stiebitz proved the full conjecture for quasi-line graphs and for graphs with independence number \(2\).
• Song’s 2022 survey is cited for further partial results.

(d: direct live-page observation) The discussion contains two comments:

1. Alfaiz, 23 July 2026: reports Song’s result for all even-hole-free graphs.

2. Quanyu Tang, 25 October 2025: points to Song’s survey, Song’s forbidden-hole theorem (arXiv:1805.11437), and Longbrake–Tariq (arXiv:2406.15164). The comment itself says the site was updated in response.

The page warns that comments are user responsibility, so I treated both as leads, not ground truth.

1. Primary-source literature check

(b) The conjecture in the live statement is the Erdős–Lovász Tihany Conjecture. Song’s 2022 survey manuscript gives the original formulation and bibliography. A 2026 primary paper by Longbrake–Tariq states that the only parameter pairs settled for arbitrary graphs are

See arXiv:2406.15164, now published as Discrete Mathematics 349 (2026), 114770.

(b) The page’s graph-class claims check out:

• Balogh–Kostochka–Prince–Stiebitz prove the quasi-line and \(\alpha(G)=2\) cases; an author-institution copy is available here.
• Song proves the stated forbidden-hole class in arXiv:1805.11437, published in Discrete Mathematics 342 (2019), 2632–2635.
• Longbrake–Tariq prove the additional claw-free cases stated in their primary manuscript.
• The newest comment is verified by Song’s 22 July 2026 manuscript arXiv:2607.20376: the conjecture holds for all even-hole-free graphs.

(b) For the \(a=2\) branch, Kawarabayashi–Pedersen–Toft’s primary paper “Double-critical graphs and complete minors” records that the Double-Critical Graph Conjecture remains open for every \(k\ge 6\), proves structural results, and in Proposition 9 proves

for every noncomplete double-critical \(k\)-chromatic graph \(H\).

(b) I also found a directly relevant prior computation that was not mentioned on problem #628. Kriesell–Pedersen state in their 2015 DMTCS paper, lines 44–46 of the introduction that they used Sage and geng to verify the Double-Critical Graph Conjecture for every graph on at most 12 vertices; their reference [13] points to a now-obsolete personal-webpage PDF. Therefore the order-\(\le12\) census below is an independent reproducibility check, not a novelty claim.

(c) A targeted search of arXiv, journal pages, the 2022 survey, the 2026 papers, and searches for “double-critical” computational censuses found no primary source claiming a general resolution, nor one reporting the order-13 \(k\ge8\) refinement below. Absence from this search does not prove novelty.

2. Elementary reduction to an exact finite search

The computation attacks the first open branch \(a=2\), \(b=k-1\), beginning with \((2,5)\) at \(k=6\).

Lemma 1 (a). A \(k\)-chromatic graph \(G\) is \((2,k-1)\)-splittable if and only if it has an edge \(xy\) such that

Proof. If such an edge exists, use \(G[\{x,y\}]\) and \(G-\{x,y\}\). Conversely, the side of chromatic number at least \(2\) contains an edge \(xy\); adding all unused vertices to the other side cannot lower its chromatic number. \(\square\)

Lemma 2 (a). If a \(K_k\)-free \(k\)-chromatic graph \(G\) is not \((2,k-1)\)-splittable, then it contains an induced, noncomplete, double-critical \(k\)-chromatic graph \(H\).

Proof. Choose an induced \(k\)-critical subgraph \(H\subseteq G\). It remains \(K_k\)-free. If \(xy\in E(H)\), nonsplittability and Lemma 1 give

On the other hand, coloring \(H-\{x,y\}\) and then giving \(x,y\) two fresh colors gives

Thus equality \(\chi(H-\{x,y\})=k-2\) holds for every edge \(xy\); this is precisely double-criticality. \(\square\)

Lemma 3 (a). Every double-critical \(k\)-chromatic graph is vertex-critical, and every noncomplete one is \(K_k\)-free.

Proof. Given a vertex \(v\), choose a neighbor \(u\). A \((k-2)\)-coloring of \(G-\{u,v\}\), with one fresh color for \(u\), shows \(\chi(G-v)\le k-1\); the reverse inequality follows from \(\chi(G)=k\). Thus deleting any vertex lowers the chromatic number. If a noncomplete \(G\) contained \(K_k\), it would have a vertex outside that clique, whose deletion would leave chromatic number at least \(k\), a contradiction. \(\square\)

Corollary 4 (b). By Proposition 9 of Kawarabayashi–Pedersen–Toft, any counterexample supplied by Lemma 2 for \(k\ge6\) has minimum degree at least \(k+1\), and hence at least \(k+2\) vertices.

This reduction is useful computationally: for order \(n\), only

need be scanned, and it is safe to enumerate the larger class of all connected graphs with \(\delta\ge k+1\), then filter it exactly.

3. Exact computation

Code: runs/erdos628_wave6g_verify.py

Completed transcripts:

• runs/erdos628_wave6g_verify.out: every feasible \(k\ge6\) through order 12.
• runs/erdos628_wave6g_n13_k8plus.out: order 13 for \(k=8,9,10,11\).

The standalone checker requires nauty-geng and a C11 compiler. The exact commands were:

python runs/erdos628_wave6g_verify.py
python runs/erdos628_wave6g_verify.py --max-n 13 --min-k 8

What the checker does

(d) For each \((k,n)\), nauty-geng -q -c -d{k+1} n generates one representative of every connected unlabeled graph with minimum degree at least \(k+1\). The installed package was nauty 2.8.8+ds-5. The scanner independently rechecks connectedness and the degree bound on every decoded graph.

(d) Each graph then passes these exact tests:

1. Two separately implemented clique searches agree on whether a \(K_k\) exists.

2. Two separately implemented coloring algorithms agree on every queried colorability predicate:

• a DSATUR branch-and-bound search;
• an independent-color-class set-partition search.

3. For a \(K_k\)-free graph of exact chromatic number \(k\), every edge \(xy\) is tested. If \(G-\{x,y\}\) is not \((k-2)\)-colorable, that edge is a verified \((2,k-1)\) split witness. If every deletion is \((k-2)\)-colorable, the graph is a double-critical survivor.

4. A third, pure-Python set-partition implementation independently recomputes every generated graph through order 10 and must match the C census exactly.

(d) No algorithm disagreement and no survivor occurred in either completed run.

Complete census through 12 vertices

Rows aggregate all shown orders for a fixed \(k\). “Generated” universes overlap between different \(k\), so they should not be summed as distinct graphs across rows.

| \(k\) | orders \(n\) | generated with \(\delta\ge k+1\) | \(K_k\)-free | exact \(\chi=k\) | verified split | double-critical survivors |

|---:|:---:|---:|---:|---:|---:|---:|

| 6 | 8–12 | 7,819,940 | 4,574,763 | 1,381,408 | 1,381,408 | 0 |

| 7 | 9–12 | 36,490 | 27,939 | 2,253 | 2,253 | 0 |

| 8 | 10–12 | 239 | 169 | 11 | 11 | 0 |

| 9 | 11–12 | 8 | 3 | 0 | 0 | 0 |

| 10 | 12 | 1 | 0 | 0 | 0 | 0 |

(d) The largest individual class was \((k,n)=(6,12)\): 7,808,882 generated graphs, of which 4,569,560 were \(K_6\)-free and 1,379,838 had chromatic number exactly 6. Every one of those 1,379,838 graphs had a verified \((2,5)\) split.

(b+d) Combining Lemma 2, the named minimum-degree theorem, and this census independently reproduces the published fact: every \((2,k-1)\) instance holds for every graph on at most 12 vertices. Equivalently, a noncomplete double-critical graph has at least 13 vertices. This is not a proof of the uniform conjecture.

Certified order-13 extension

| \(k\) | generated with \(\delta\ge k+1\) | \(K_k\)-free | exact \(\chi=k\) | verified split | double-critical survivors |

|---:|---:|---:|---:|---:|---:|

| 8 | 124,380 | 114,178 | 2,543 | 2,543 | 0 |

| 9 | 334 | 269 | 11 | 11 | 0 |

| 10 | 7 | 3 | 0 | 0 | 0 |

| 11 | 1 | 0 | 0 | 0 | 0 |

(b+d) Consequently, if a noncomplete double-critical graph on 13 vertices exists, its chromatic number is exactly \(6\) or \(7\). Values \(k\le5\) are excluded by the known theorem, \(k=8,\ldots,11\) by the table, and \(k\ge12\) by the necessary order bound \(n\ge k+2\).

4. Independent checks and reproducibility record

(d) The completed full-\(\le12\) run took 21.28 wall seconds; the \(n=13,k\ge8\) run took 1.05 wall seconds. The output contains per-class FNV-1a graph-stream hashes as well as all counts.

Final SHA-256 values:

f9b68360817f2da8cbdd83ea26942a86500891c52e35927c1b152ba837ac8e73  runs/erdos628_wave6g_verify.py
ca8e34f428f06a26c6c9c839cdca77be0e105876280a7d4ab48a9b2a60dceef9  runs/erdos628_wave6g_verify.out
0323e315b5b5f38bc1f2919f824c94967d1326e23287630a9fd801b1bde26aa7  runs/erdos628_wave6g_n13_k8plus.out

(d) As an additional universe-count check, complement generation for the \(k=6,n\le12\) classes (geng -D(n-k-2)) reproduced the respective candidate counts

This uses the bijection \(G\mapsto\overline G\), under which \(\delta(G)\ge k+1\) is equivalent to \(\Delta(\overline G)\le n-k-2\).

Trust boundary. (d) Graph property decisions are recomputed from graph6 data by the supplied source, with two exact algorithms for every crucial predicate. Exhaustive generation up to isomorphism still relies on the standard correctness of nauty geng; this is not a formally verified enumeration.

5. Exact remaining wall

(d) I attempted \((k,n)=(7,13)\), but stopped it after 199 seconds at the promised compute cap. The partial transcript is labeled runs/erdos628_wave6g_n13_k7.partial.out and makes no mathematical claim.

(c) A \(1/1000\) generation shard for \((k,n)=(7,13)\) produced 74,302 graphs; this suggests roughly \(7.4\times10^7\) candidates, but shard balance is not guaranteed. Completing this class with the current doubly checked scanner would require more than the measured 199 seconds and was not extrapolated into a result.

(c) For \((k,n)=(6,13)\), a \(1/1000\) shard generated 10,607,826 graphs in 5.95 seconds. A naive full scan therefore has roughly \(1.06\times10^{10}\) candidates. Using the measured \(k=6,n=12\) scanner throughput gives an estimate of about 7.5 scanner core-hours plus about 1.7 generator core-hours, roughly 9 core-hours total. I did not run it.

(b) The exact missing lemma for the \(a=2\) branch remains: prove that no noncomplete double-critical \(k\)-chromatic graph exists for \(k\ge6\). The finite census cannot supply the uniform/finiteness step. For the full Erdős–Lovász Tihany Conjecture, the other unsolved parameter pairs require additional ideas beyond double-criticality.

(c) A practical next finite step is to use the stronger known local structure around degree-\((k+1)\) vertices to prune the two order-13 classes before coloring. Even a complete order-13 census, however, would still be only finite evidence.

PARTIAL: Independently reproduced the known double-critical census through 12 vertices and certified that any order-13 noncomplete double-critical graph must be 6- or 7-chromatic; the general Erdős–Lovász Tihany conjecture remains open.