Skip to content

Erdős Problem #1104

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, chromatic number.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

How many colours might a graph need if it has no triangles?

The chromatic number \(\chi(G)\) is the fewest colours needed to colour vertices so that no edge joins vertices of the same colour. A triangle-free graph cannot contain three vertices all mutually adjacent. Erdős Problem #1104 asks for

\[ f(n)=\max\{\chi(G):|V(G)|=n,\ G\text{ triangle-free}\}. \]

The main open issue is the sharp constant in its large‑\(n\) growth, not whether high-chromatic triangle-free graphs exist.

A small example

The five-vertex cycle \(C_5\) contains no triangle but needs three colours. Applying the classical Mycielski construction adds five companion vertices and an apex, yielding a graph with

\[ |V|=11,\qquad |E|=20,\qquad \chi(G)=4. \]

An exact program enumerates all its triangles and finds zero, then uses chromatic backtracking to verify no three-colouring exists and a four-colouring does. Thus \(f(11)\ge4\). This is a finite illustration, not a proof of the asymptotic optimal constant.

What is known

The maintained catalogue reports the sharpest bounds currently incorporated there:

\[ (1-o(1))\sqrt{\frac n{\log n}} \ \le f(n)\le\ (2+o(1))\sqrt{\frac n{\log n}}. \]

The upper bound is attributed to Davies and Illingworth (2022), and the lower bound to Hefty, Horn, King and Pfender (2025). The published Davies–Illingworth journal abstract confirms an improvement by a factor \(\sqrt2\) over the earlier \(2\sqrt2\) upper constant.

The order \(\sqrt{n/\log n}\) is therefore established. Determining the limiting sharp leading coefficient remains open.

There is also an analogous edge-count problem, with extremal order roughly \((m/(\log m)^2)^{1/3}\). It has a different parameter and is not interchangeable with \(f(n)\).

GCL's current state

Authenticated source audit #2375 records the source constants and the exact 11-vertex verification. The frozen formal-conjectures file has declarations for known upper and lower bounds, but unresolved proof bodies; it does not settle the optimal constant.

This article belongs to the predetermined 20 critical-review sample. Its full primary mathematical and editorial review is still pending.

What remains

Read the complete Davies–Illingworth and Hefty–Horn–King–Pfender arguments, inspect their \(o(1)\) quantifiers and constants, compare vertex and edge formulations, and independently assess the manuscript against these sources before marking the critical review complete.

Sources and claim boundaries

Erdős Problem #1104, OPEN; Davies–Illingworth (2022); Hefty–Horn–King–Pfender (2025) as cited in the maintained catalogue; GCL return #2375. Exact finite chromatic computation is independent, but the asymptotic bounds are external. Critical review and admission remain pending.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2375 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction