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; \]

2. 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\);

2. 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:

| \(n\) | independently verified \(f(n)\) | reason |

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

| \(1\) | \(1\) | one vertex |

| \(2\le n\le4\) | \(2\) | \(K_2\); triangle-free non-bipartite graphs need an odd cycle of length at least \(5\) |

| \(5\le n\le10\) | \(3\) | \(C_5\); exhaustive \(h_3(4)=11\) |

| \(11\le n\le18\) | \(4\) | Grötzsch graph; exhaustive \(h_3(5)\ge19\) |

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.