Erdős problem #1104: live check, an exact finite audit, and the constant-\(2\) barrier

Access/search date: 2026-07-27 UTC.

Result in one paragraph

The live problem is open and the collision gate did not fire. The current asymptotic interval is

I did not improve either asymptotic constant. I did obtain two fully reproducible outputs:

1. an independent finite computation proving \(h_3(4)=11\) and

\(h_3(5)\ge 19\), where \(h_3(k)\) is the least order of a triangle-free \(k\)-chromatic graph; consequently \[ f(1)=1,\quad f(2\ldots4)=2,\quad f(5\ldots10)=3,\quad f(11\ldots18)=4; \]

1. a sharp diagnosis of the standard asymptotic proof. A

maximum-degree threshold \(a\sqrt{n\log n}\), Molloy's \((1+o(1))\Delta/\log\Delta\) theorem, and one-color neighborhood deletion force \[ C\ge\max\{2a,2/a\}\ge2. \] Thus that proof skeleton cannot lower the current constant \(2\).

The finite bound independently recovers Avis's published \(1979\) lower bound; it is not claimed as a new theorem. The value \(h_3(5)=22\) and the stronger bound \(h_3(6)\ge32\) are already known from substantially larger published computations, but they were not re-executed here.

Claim labels used below:

• [A] elementary-rigorous;
• [B] rigorous modulo an explicitly named theorem;
• [C] plausible/structural-unverified;
• [D] computational-only.

0. Mandatory live-page gate

I fetched the live page, its LaTeX view, the discussion thread, and the original-reference pop-up through a Bright Data residential browser. Direct datacenter access was not used for this gate.

The rendered live state was:

• status OPEN;
• 0 claimed proofs for this problem;
• Interested in collaborating None;
• Currently working on this problem None;
• last page edit 21 January 2026.

Therefore the required stop rule did not fire.

Verbatim live statement

Let \(f(n)\) be the maximum possible chromatic number of a triangle-free graph on \(n\) vertices. Estimate \(f(n)\).

Everything mathematical listed on the live page

The page gives the current bounds

It attributes the upper bound to Davies--Illingworth and the lower bound to Hefty--Horn--King--Pfender.

For the edge analogue \(g(m)\), the page records

from Davies--Illingworth, and

from Kim. The LaTeX view confirms that the first constant is \(3^{5/3}\); the rendered plain-text extraction visually compresses it. The page also says that \(f\) is inverse to the function \(h_3\) in problem #1013 and points to problem #920 for a generalization. It lists OEIS A292528 and says that a formalized statement exists.

The reference pop-up identifies [Er67c] as P. Erdős, Some remarks on chromatic graphs, Colloq. Math. 16 (1967), 253--256. The primary scan and publisher record exist; the DOI is 10.4064/cm-16-1-253-256.

Both displayed comments

The thread contained exactly two comments, both dated 27 October 2025.

• Desmond Weisenberg says the problem is essentially a duplicate of #1013.
• Wouter Cames van Batenburg supplies context about the earlier fractional

chromatic bounds, the later Martinsson--Steiner fractional result, and possible constants for the ordinary chromatic number. This is explicitly speculation, not a proof claim. The comment suggests \(\sqrt2\), and more speculatively \(1\), as possible upper constants. It also asks whether the leading constant in the maximum-degree Johansson--Molloy theorem could be reduced from \(1\) to \(1/2\).

The comment's “this paper” link is the primary Cames van Batenburg--de Joannis de Verclos--Kang--Pirot paper, DOI 10.37236/8650. Its Martinsson--Steiner link is the primary Forum of Mathematics, Sigma article, DOI 10.1017/fms.2025.10112.

This section is [A] as a faithful transcription of what was displayed, not an endorsement of unverified comments.

1. Primary-source literature audit

The current upper bound

Davies and Illingworth, “The \(\chi\)-Ramsey problem for triangle-free graphs”, arXiv:2107.12288v2, exists and is the cited paper. Its Theorem 1 states

for every \(n\)-vertex triangle-free graph. It also gives the displayed edge bound. [B]

The paper's proof has two ingredients:

1. if \(\Delta(G)\) is small, apply Molloy's theorem

\(\chi(G)\le(1+o(1))\Delta/\log\Delta\);

1. if a vertex has large degree, give its independent neighborhood one

color, remove that neighborhood, and use induction.

This proof architecture is used explicitly in Section 2 of the paper and is analyzed in Section 6 below.

The current lower bound

Hefty, Horn, King, and Pfender, “Improving \(R(3,k)\) in just two bites”, arXiv:2510.19718, exists. The current version is v3, revised 19 February 2026. Theorem 1.2 gives

and the more directly useful Theorem 1.3 says that for every fixed \(\varepsilon>0\) and all sufficiently large \(n\), there is an \(n\)-vertex triangle-free graph \(G\) with

Since every color class is independent,

Letting \(\varepsilon\to0\) gives exactly the live lower constant \(1\). The implication is [A]; the construction theorem is [B].

The fractional results in the comment do not settle ordinary coloring

Martinsson and Steiner's Theorem 1.4 proves

for all \(n\)-vertex triangle-free \(G\), and Theorem 1.5 gives the edge constant \(18^{1/3}\). These are the fractional chromatic number, not the ordinary chromatic number. [B]

A targeted 2026 search also found Abhishek Dhawan, “Fractional coloring via entropy”, arXiv:2603.17730v2 (13 April 2026). Its abstract concerns fractional coloring of locally colorable degenerate graphs and uniform hypergraphs; it does not claim an improved ordinary bound for \(f(n)\).

I searched the exact problem wording, “\(\chi\)-Ramsey” terminology, the two current constants, and 2025--2026 triangle-free coloring papers. I found the sources above but no primary source claiming an improvement to either ordinary-chromatic constant, much less a solution. This is an honest search result, not a proof of bibliographic completeness. [C]

Known finite values

Write \(h_3(k)\) for the least number of vertices in a triangle-free graph of chromatic number \(k\). The following primary sources exist:

• Chvátal, The minimality of the Mycielski graph, Lecture Notes in

Mathematics 406 (1974), 243--246, proves \(h_3(4)=11\).

• Avis,

“On minimal 5-chromatic triangle-free graphs”, DOI 10.1002/jgt.3190030411, proves \(h_3(5)\ge19\).

• Jensen and Royle,

“Small graphs with chromatic number 5: A computer search”, DOI 10.1002/jgt.3190190111, prove \(h_3(5)=22\).

• Goedgebeur,

“On minimal triangle-free 6-chromatic graphs”, arXiv:1707.07581, proves \(32\le h_3(6)\le40\) by computational methods and independently confirms the complete small \(5\)-chromatic census.

Thus the published, computation-dependent small values are

In particular the published literature implies the exact \(f(n)\) table through \(31\):

These statements are [B] for the mathematical conclusions and [D] for the exhaustive portions of the named papers. My own smaller recomputation below does not purport to re-run the Jensen--Royle or Goedgebeur searches.

2. Exact inverse formulation

For positive integers \(n\),

Indeed, a \(k\)-chromatic triangle-free graph on \(h_3(k)\) vertices can be padded with isolated vertices, while any \(n\)-vertex witness to \(f(n)\ge k\) contains a \(k\)-critical subgraph on at most \(n\) vertices. [A]

Equation (2.1) makes finite results about \(h_3\) legitimate exact small cases of the live function \(f\), but no finite table can determine the asymptotic constant.

3. Critical-neighborhood reduction for \(h_3(5)\)

This section gives the complete reduction used by the checker.

Lemma 1: critical graph facts

If a triangle-free graph has chromatic number at least \(5\), it contains a \(5\)-critical subgraph \(G\). Such a \(G\) is connected and \(\delta(G)\ge4\). By Brooks's theorem, \(\Delta(G)\ge5\): a connected graph of maximum degree at most \(4\) is \(4\)-colorable unless it is \(K_5\) or an odd cycle, neither of which is a triangle-free \(5\)-chromatic graph. [B for Brooks; A for the remaining deductions.]

Choose \(v\) of maximum degree \(d\), put

The set \(S\) is independent. If \(H\) were \(3\)-colorable, color \(H\) with colors \(1,2,3\), color every vertex of \(S\) with color \(4\), and give \(v\) color \(1\). This would \(4\)-color \(G\), a contradiction. Since \(H\) is a proper subgraph of the \(5\)-critical graph \(G\), it is \(4\)-colorable. Therefore

Using \(h_3(4)=11\),

Consequently no such \(G\) has at most \(16\) vertices. For orders \(17\) and \(18\), \(d\ge5\) and (3.2) leave exactly three cases:

All of this is [A] once Brooks and \(h_3(4)=11\) are supplied.

Lemma 2: classifying the bases \(H\)

The exhaustive order-\(11\) check finds one triangle-free non-\(3\)-colorable graph: the Grötzsch graph, the Mycielskian of \(C_5\).

For \(|H|=12\) and \(d=5\), note that \(\Delta(H)\le5\). Choose a minimal induced \(4\)-chromatic subgraph \(J\subseteq H\). Then \(J\) is \(4\)-vertex-critical and \(|J|\in\{11,12\}\).

• If \(|J|=11\), then \(J\) is the Grötzsch graph. The twelfth vertex

may be joined to any independent subset of \(J\) that preserves maximum degree at most \(5\).

• If \(|J|=12\), then \(H=J\). Exhaustively generating connected

triangle-free graphs of minimum degree at least \(3\), testing \(4\)-chromaticity, and testing every vertex deletion finds four such \(4\)-vertex-critical cores.

There are \(92\) labeled one-vertex extensions of the explicit Grötzsch graph, \(17\) up to isomorphism. Together with the four order-\(12\) critical cores, this gives \(21\) possible \(H\)'s. [D]

The classification argument is [A] conditional on the exhaustive order-\(11\) and order-\(12\) lists.

Lemma 3: the coloring obstruction is a finite set-cover problem

For each \(s\in S\), let

Each \(A_s\) is independent, or an edge inside \(A_s\) would form a triangle with \(s\). Criticality gives \(\deg(s)\ge4\), while \(v\) has maximum degree \(d\), so

Fix a proper \(4\)-coloring \(c\) of \(H\), and propose color \(r\) for \(v\). A vertex \(s\in S\) can receive any color \(q\ne r\) which is absent from \(c(A_s)\). Since \(S\) is independent, these choices do not interfere. Thus \(c\) and \(r\) fail to extend precisely when at least one \(A_s\) contains all three colors other than \(r\).

Define the universe

Every allowed independent set \(A\) defines a subset of \(\mathcal U\): the pairs \((c,r)\) for which \(A\) sees all three colors other than \(r\). If \(G\) is not \(4\)-colorable, its \(d\) sets \(A_s\) must cover all of \(\mathcal U\). [A]

The checker solves a relaxation: it ignores degree capacities on vertices of \(H\), ignores criticality conditions beyond (3.4), and asks only whether any at most \(d\) allowed masks cover \(\mathcal U\). Infeasibility of this relaxed problem proves nonexistence of \(G\).

Coverage masks contained in another mask may be discarded. This preserves minimum cover size: replace a selected nonmaximal mask by a maximal superset, or delete it if that superset is already selected. [A]

4. Exact computation and output

The standalone verifier is runs/erdos1104_wave6u_reverify.py. It uses no downloaded graph lists and no Python graph or SAT package. It implements:

• graph6 encoding and decoding;
• exact \(k\)-colorability backtracking;
• enumeration of every proper \(4\)-color partition modulo color names;
• independent-set enumeration and the set-cover check;
• the explicit \(C_5\) and Grötzsch witnesses.

It invokes Debian nauty 2.8.8's geng only to generate all nonisomorphic connected triangle-free graphs with the specified minimum degree, and labelg only for canonical labeling. The completeness claim is therefore [D], conditional on nauty's exhaustive generator, rather than a formal proof certificate.

Run:

python3 runs/erdos1104_wave6u_reverify.py

Observed complete output:

generator=/bin/nauty-geng
canonical_labeler=/bin/nauty-labelg
h4_enumeration=[{"n":4,"candidates":0,"non3colorable":0},{"n":5,"candidates":0,"non3colorable":0},{"n":6,"candidates":1,"non3colorable":0},{"n":7,"candidates":1,"non3colorable":0},{"n":8,"candidates":8,"non3colorable":0},{"n":9,"candidates":23,"non3colorable":0},{"n":10,"candidates":209,"non3colorable":0},{"n":11,"candidates":2052,"non3colorable":1}]
VERIFIED h_3(4)=11
order12_core_enumeration={"connected_triangle_free_min_degree_3":36223,"non3colorable":14,"vertex_critical_4chromatic":4}
order12_bases={"labeled_grotzsch_extensions":92,"unlabeled_grotzsch_extensions":17,"critical_cores":4,"union":21}
cover_cases=23
cover_transcript_sha256=36072c15077b58fdd78fe8e965a5d715c8c0dfa59bb317695e1a50d0bc785b64
cover_summary={"total_color_partitions":24394,"total_maximal_masks":713,"total_combinations_checked":11163328,"covers_found":0}
VERIFIED h_3(5)>=19
VERIFIED f(1)=1; f(2..4)=2; f(5..10)=3; f(11..18)=4
elapsed_seconds=12.445

The measured wrapper statistics were 12.51 wall seconds, 100% of one CPU, and 37,252 KiB maximum resident memory. The source file has SHA-256

9af9626fb4ae2b1f1f5d5056640541886e7f099582bb20cda875142b0797e479

Exact independently checked table

The witnesses are \(K_2\), \(C_5\), and the 11-vertex Grötzsch graph, padded by isolates. The upper bounds are the absence of an odd cycle on fewer than five vertices, \(h_3(4)=11\), and \(h_3(5)\ge19\). Therefore:

The elementary entries are [A] and both exhaustive thresholds are [D].

5. Why the finite computation stops here

At order \(19\), the critical-neighborhood reduction introduces a \(13\)-vertex \(4\)-chromatic base when \(d=5\); at order \(20\), bases of order as large as \(14\) occur. Goedgebeur's published Table 3 lists the numbers of triangle-free \(4\)-chromatic graphs as

The current run processed 23 cover cases in 12.45 seconds, about 0.54 CPU-second per case, although larger bases generally have more colorings and should be slower. A naive all-base extrapolation is therefore roughly:

• order \(14\): at least \(11\) core-hours; realistically

\(10\)--\(50\) core-hours after overhead;

• order \(15\): at least \(970\) core-hours; realistically

\(10^3\)--\(5\times10^3\) core-hours.

At a representative preemptible CPU rate of about USD \(0.04\) per core-hour, those ranges are roughly USD \(0.40\)--\(2\) and USD \(40\)--\(200\), respectively. I did not run them. Better critical-extension generation would reduce the candidate count, but would also require a new completeness audit.

For comparison, Goedgebeur reports approximately 13 CPU-years for the complete maximal-triangle-free computation underlying the census through 24 vertices. This is why the published exact value \(h_3(5)=22\) is cited rather than casually re-run here.

This finite wall is [D] and does not bear on the asymptotic constant.

6. The exact barrier in the standard asymptotic machinery

This gives a separate, uniform diagnosis of why the natural proof attempt does not improve the live upper bound.

Suppose the Davies--Illingworth induction uses the threshold

and seeks

Low maximum degree

If \(\Delta(G)\le T(n)\), Molloy's theorem gives

because \(\log T(n)=(\tfrac12+o(1))\log n\). Hence this branch needs

High maximum degree

If some vertex has degree at least \(T(n)\), its neighborhood is independent. Color it with one color and induct on at most \(n-T(n)\) vertices. The target function must pay for that color:

Taylor expansion, with \(T(n)=o(n)\), gives

Thus this branch needs

Combining (6.1)--(6.2),

with equality at \(a=1\). This is an elementary-rigorous obstruction to this specified proof template, not a lower bound on the true \(f(n)\). [A]

More generally, if the low-degree theorem were improved to

the same optimization would give

Therefore:

• \(q=1/2\) would permit \(C=\sqrt2\) in this skeleton;
• \(q=1/4\) would permit \(C=1\).

This precisely explains why the comment's speculative leading \(1/2\) maximum-degree theorem would reach the fractional \(\sqrt2\) constant but not the lower constant \(1\).

The alternatives are equally precise: improve the local \(\Delta/\log\Delta\) constant, or replace one-color neighborhood peeling with a method that removes more vertices per integral color. The Martinsson--Steiner fractional result alone supplies neither operation; turning its probability distribution on independent sets into an efficient partition is the missing integral step. A useful theorem would have to exploit graphs near the extremal \(n\)-vertex scale, not merely assert a general bounded integrality gap.

7. Honest final state

The lower construction has reached constant \(1\), while the best ordinary-coloring upper theorem remains at \(2\). The independently verified finite result is exact but already subsumed by known small-graph literature. The genuinely missing uniform ingredient is now isolated: one must beat either the leading constant \(1\) in the relevant maximum-degree coloring input, or the efficiency of deleting one independent neighborhood per color. No computation performed here bridges that asymptotic gap, and nothing here closes problem #1104.

PARTIAL: Independently verified \(h_3(4)=11\), \(h_3(5)\ge19\), and exact \(f(n)\) through \(n=18\); proved the Davies--Illingworth threshold/peeling template cannot beat constant \(2\), but did not improve the open asymptotic bounds.