Skip to content

Erdős Problem #738

Editorial depth: Reviewed explanatory article — evidence qualified.
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.

The question in plain language

Erdős Problem #738, attributed to Gyárfás, asks whether EVERY triangle-free graph with INFINITE chromatic number contains every finite tree as an induced subgraph. Induced means that the selected vertices have exactly the edges of the chosen tree, not extra chords. The problem remains OPEN.

A small example

A five-cycle C₅ is triangle-free and requires three colours. It contains an induced three-vertex path but not an induced four-vertex star K₁,₃, since all its vertices have degree two. This is not a counterexample: C₅ has finite chromatic number.

What is known

In a triangle-free graph, all neighbors of a fixed vertex are pairwise nonadjacent; hence any vertex of degree at least k generates an induced star K₁,k. Infinite chromatic number forces unbounded finite degrees (otherwise a finite greedy colouring exists, using compactness in the infinite case). This proves all finite stars occur as induced subgraphs but does not prove every finite tree occurs. A broad Gyárfás–Sumner tree-free chromatic boundedness conjecture is closely related but must not be assumed established in full.

GCL's current state

The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.

Preserved source-review qualifications: gyarfas triangle free infinite chromatic induced trees open; finite c5 cannot resolve. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

Source-lock the historic Gyárfás formulation, prove an induced-tree lemma for one additional tree class, and state clearly which external finite-graph chromatic bounds are known versus conjectured. Complete original proof review and protected editorial admission.

Sources and claim boundaries

Maintained #738; GCL source report. Original Er81/Gyárfás complete papers not inspected; no new general theorem, protected merge or V2 admission.

Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2009 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider 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