Skip to content

Erdős Problem #1092

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

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

Suppose every small part of a graph can be made easy to colour by removing relatively few edges. Does that guarantee the whole graph needs only a few colours?

Erdős Problem #1092 studies this local-to-global question. Fix \(r\ge2\). If every \(m\)‑vertex subgraph can be decomposed into an \(r\)‑colourable graph and a graph with at most \(f_r(m)\) edges, when can we conclude the original graph is \((r+1)\)‑colourable?

The conjecture was that a linear deletion allowance of order \(f_r(m)\gg_r m\) might suffice. This turned out to be false.

A small example

Consider \(K_4\). Split its vertices into two classes of two. Four edges run between the classes, forming the bipartite graph \(K_{2,2}\). The two remaining edges lie within classes.

Deleting those two edges makes the entire graph bipartite. Yet \(K_4\) itself requires four colours. This elementary example shows the decomposition concept, but does not refute the linear conjecture: that needs arbitrarily large graphs with stringent conditions on every subgraph.

What is known

The maintained catalogue attributes a strong disproof to Rödl (1982). For any prescribed small \(\varepsilon>0\) and arbitrarily large target chromatic number, the reported construction gives graphs that remain highly chromatic even though every subgraph on \(m\) vertices can be made bipartite by deleting at most \(\varepsilon m\) edges.

Because \(\varepsilon\) can be arbitrarily small, no fixed positive linear allowance forces bounded global chromatic number in the manner conjectured.

GCL's current state

Authenticated source audit #2363 records the quantifiers and independently counts the four bipartite and two deleted edges of \(K_4\).

The frozen formal-conjectures file labels the statement disproved but contains unproved theorem bodies. GCL has not independently reconstructed Rödl's construction or kernel-verified a proof.

What remains

Review Rödl's original theorem, the phrase “every subgraph,” and the exact dependence on \(\varepsilon\) and target chromatic number. A finite local decomposition cannot replace a proof for arbitrarily small deletion coefficients.

Sources and claim boundaries

Erdős Problem #1092; Erdős (1976), p. 4; Rödl (1982), externally cited counterexamples; GCL source return #2363. Published mathematical disproof externally reported, not independently proved here. This manuscript is unaccepted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2363 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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