Rödl 1982 — the hypergraph analogue of Erdős–Hajnal–Szemerédi's almost-bipartite large-chromatic-number problem, SOLVED (the graph case, erdos/74, remains open)

Statement

**The general (still-open, graph) problem, Erdős–Hajnal–Szemerédi 1982 [EHS82] — Erdős #74 — almost-bipartite graph of infinite chromatic number.** Let $f(n)\to\infty$, possibly arbitrarily slowly. Is there a graph $G$ of infinite chromatic number such that every finite induced subgraph of $G$ on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?

The hypergraph analogue — the target of this page, SOLVED by Rödl. Rödl, "Nearly bipartite graphs with large chromatic number," *Combinatorica* 2 (1982), 377–383 [Ro82], considers the natural generalization: replace "graph" by "3-uniform hypergraph" and "bipartite" by 2-colorable (a hypergraph is 2-colorable, i.e. has *property B*, if its vertices can be 2-colored so that no edge is monochromatic — the hypergraph substitute for "bipartite," since a graph is bipartite iff it is 2-colorable in this same sense with edges of size 2). The hypergraph question is: for every $f(n)\to\infty$ (arbitrarily slowly), does there exist a 3-uniform hypergraph $H$ of infinite chromatic number such that every $n$-vertex sub-hypergraph of $H$ can be made 2-colorable by deleting at most $f(n)$ edges? Rödl proved yes, in full generality of $f$ (erdosproblems.com/74, direct quote: "Rödl [Ro82] has proved this for hypergraphs").

**A closely related, also-solved finite/linear sub-case (still Rödl 1982), for ordinary graphs — erdos/1092.** Rödl additionally settled, for graphs (not hypergraphs), the restricted *linear* version: for every fixed $\epsilon>0$ and every $k$, there is a graph $G_{\epsilon,k}$ with $\chi(G_{\epsilon,k})\ge k$ (in fact one can push $\chi=\aleph_0$) such that every $m$-vertex subgraph of $G_{\epsilon,k}$ can be made bipartite by deleting at most $\epsilon m$ edges. This is a strictly weaker statement than the general $f(n)\to\infty$-arbitrarily-slowly problem (linear $f(n)=\epsilon n$ is a much more generous allowance than, say, $f(n)=\sqrt n$ or $f(n)=\log n$), but it fully and negatively resolves the *prior* question of Erdős and Hajnal that motivated [EHS82]: is there a universal constant $\epsilon_0>0$ such that "$\epsilon_0$-close to bipartite" forces $\chi\le 3$? Rödl's construction shows no such $\epsilon_0$ exists — you can be $\epsilon$-close to bipartite (any fixed $\epsilon>0$) and have unboundedly large, even infinite, chromatic number. (Per a Google-Scholar-indexed abstract snippet of [Ro82], Lovász independently found a different construction giving the same negative answer to the Erdős–Hajnal $\epsilon_0$ question — not independently verified beyond this snippet.)

Facts

- What remains open (this is *not* what Rödl solved): the general graph statement Erdős #74 — almost-bipartite graph of infinite chromatic number for arbitrary $f(n)\to\infty$ — in particular already unresolved for $f(n)=\sqrt n$ or any $f(n)=o(n)$. Erdős offered \$500 for a "yes" proof, \$250 for a counterexample (erdosproblems.com/74), an asymmetry signalling he expected "yes." As of the live erdosproblems.com page (last edited 25 Jan 2026, 0 forum comments), this remains completely open — the 44-year gap between Rödl's 1982 linear ($\epsilon n$) upper bound for graphs and the fully-general sub-linear conjecture has not been closed. Rödl's *full* solution of the analogous problem is specifically for hypergraphs, not ordinary graphs — going from 3-uniform hypergraphs back down to graphs (uniformity 2) for the general-$f$ statement is exactly the open gap. - Why hypergraphs are more tractable here than graphs. For graphs, "$\ge 1$ edge deleted per bad odd cycle" is a hard, essentially one-edge-per-violation constraint once cycles start overlapping in complex ways; property-B violations in a 3-uniform hypergraph (monochromatic edges under any 2-coloring) admit more construction freedom because 2-colorability of 3-uniform hypergraphs is itself a richer, more "loosely constrained" combinatorial target than graph-bipartiteness (a triangle-free-like local condition is not required the same way an odd-cycle-free condition is for graphs) — this is a plausible qualitative explanation for why the hypergraph case fell to Rödl's 1982 techniques while the graph case has resisted 44+ years of subsequent attention; flagged as informed structural reasoning, not a claim independently verified against Rödl's actual proof text. - Timing relative to the Rödl nibble. [Ro82] (1982) predates "the Rödl nibble" semi-random/iterated-random-deletion method, whose founding papers are V. Rödl, "On a packing and covering problem," *European J. Combin.* 6 (1985), 69–78, and Frankl–Rödl, "Near perfect coverings in graphs and hypergraphs," *European J. Combin.* 6 (1985), 317–326 (see Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings) — a different result by the same author, three years later, solving a different problem (asymptotically-optimal covering/packing designs, the Erdős–Hanani conjecture). Do not conflate the two: [Ro82]'s "nearly bipartite" construction is not an instance of "the Rödl nibble," and nothing in the sources found here indicates it uses semi-random iterated sparsification of that specific later-invented kind. - **Sibling result disproving a size-critical-graph analogue (also *not* [Ro82], flag against conflation): Rödl & Tuza 1985 — erdos/744.** A separate, later paper (J. Rödl, Zs. Tuza, cited on erdosproblems.com/744 as [RoTu85]) disproved a different-but-thematically-adjacent 1982 EHS82 conjecture, that $f_k(n)$ (min. edges to delete to bipartite-ify a *vertex-critical* $k$-chromatic graph on $n$ vertices) must $\to\infty$ with $n$; Rödl–Tuza showed instead $f_k(n)=\binom{k-1}2$, a *constant* independent of $n$, for large $n$. Gallai (1968) had already shown $f_4(n)\ll n^{1/2}$ and Lovász extended this to $f_k(n)\ll n^{1-1/(k-2)}$ (both explicit constructions, pre-dating and setting up the Rödl–Tuza disproof). These Gallai/Lovász constructions are the closest directly-documented, explicit technique instances in this whole problem cluster and are plausible methodological ancestors of [Ro82]'s own construction, given the shared authorship circle (Erdős–Hajnal–Szemerédi conjectured both; Lovász is independently credited with an alternative negative-answer construction for the [Ro82] question itself, per the abstract snippet above) — this connection (Gallai/Lovász's explicit critical-graph constructions as a technical ancestor of Rödl's 1982 construction) is inference, not a sourced claim. - **Contrast that bounds how far this technique family can go: Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$. Even allowing $f(n)\gg n$ (i.e. dropping the "nearly bipartite" constraint almost entirely), the analogous statement is false** once chromatic number is pushed from $\aleph_0$ (countable — Rödl's/[EHS82]'s regime) up to $\aleph_1$: any graph with $\chi(G)=\aleph_1$ must contain, for some fixed odd cycle length $2r+1$, uncountably many pairwise vertex-disjoint copies, forcing $h_G(n)\gg n$ unconditionally (erdosproblems.com/111, direct-fetch quote). This is a hard structural ceiling — no construction technique, however clever, can push a $\ge\aleph_1$-chromatic graph below linear edit-distance-to-bipartite. It sets the scale of what Rödl's countable-chromatic constructions are working *within*: staying at $\chi=\aleph_0$ is not a simplification chosen for convenience, it is *necessary* for any sub-linear-$f$ hope to survive at all.

Solution

Answer: YES for hypergraphs, in full generality. For every $f(n)\to\infty$ (arbitrarily slowly), Rödl constructed a 3-uniform hypergraph $H$ with $\chi(H)=\aleph_0$ such that every $n$-vertex sub-hypergraph of $H$ can be made 2-colorable (property B) by deleting at most $f(n)$ edges. This is stated without qualification on erdosproblems.com/74 ("Rödl [Ro82] has proved this for hypergraphs") — i.e., unlike the graph case, no linear-only restriction is recorded; the hypergraph problem is closed.

Proof technique — the transferable idea, with confidence explicitly split from the facts above.

What is *directly sourced*: [Ro82]'s stated aim (per the Google-Scholar abstract snippet) is "(1) give a negative answer to [the Erdős–Hajnal constant-$\epsilon$⇒$\chi\le3$ question] and (2) consider the analogous problem for hypergraphs" — i.e. the paper is explicitly framed as *one* argument transported across two settings (finite graphs with a fixed $\epsilon$, then hypergraphs with a fully general $f(n)\to\infty$), not two unrelated arguments. This strongly suggests a single underlying construction schema, parametrized so that it degrades gracefully: tune the same construction's parameters to get (a) a finite $\chi\ge k$, $\epsilon$-nearly-bipartite graph for every fixed $(\epsilon,k)$ [the graph/erdos/1092 result], and separately (b) — where hypergraphs give the construction enough extra freedom — push all the way to *infinite* chromatic number while letting the "nearly bipartite" slack $f(n)$ itself go to infinity arbitrarily slowly, rather than being pinned to a fixed linear rate $\epsilon n$.

The general schema this class of result follows (attested pattern across [EHS82]/[Ro82]/Gallai/Lovász's shared problem cluster, *not* independently confirmed as the literal content of Rödl's proof — treat as the best-supported reconstruction, not a citation):

1. Build a family of finite, explicit high-chromatic "almost-bipartite" gadgets, one for each target chromatic number $k$. The Gallai (1968, $f_4(n)\ll n^{1/2}$) and Lovász ($f_k(n)\ll n^{1-1/(k-2)}$) constructions for the sibling critical-graph problem erdos/744 are the one directly documented instance of "an explicit finite graph, provably $k$-chromatic (or with property-B failing by design in the hypergraph case), that needs only a sublinear/small number of edge deletions to become bipartite/2-colorable" in this literature — i.e. exactly the kind of building block a construction like Rödl's would need, whether or not Rödl's own gadget is literally these ones. 2. Amalgamate/stack an increasing sequence of these finite gadgets ($G_1, G_2, G_3,\dots$ with $\chi(G_k)\ge k$) into one infinite structure whose global chromatic number is $\sup_k \chi(G_k)=\aleph_0$, while controlling how the "edit distance to bipartite/2-colorable" of an $n$-vertex sub-structure grows — the standard move (also seen in this wiki's The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs for a structurally analogous "build then locally repair" pattern, and in Erdős–Hajnal shift graphs (explicit high-chromatic, controlled-odd-girth construction) as a standard explicit high-chromatic building block) for turning "for every $k$ there's a finite gadget" into "there's one infinite object with unbounded/infinite chromatic number." The technical crux is ensuring that as you stack more and larger gadgets, an *arbitrary* $n$-vertex window into the whole structure — which may straddle several gadgets, not just sit inside one — still only needs $f(n)$, not $\Omega(n)$, edges deleted; this is precisely where letting $f(n)\to\infty$ arbitrarily slowly (rather than demanding a fixed rate) buys the room needed to make the amalgamation work, and is the likely reason the *hypergraph* case (with strictly more design freedom in how "2-colorable-with-few-deletions" gadgets can be shaped and glued) closed in full while the *graph* case has stayed stuck at the linear ($\epsilon n$) rate for over 40 years. 3. This predates the semi-random/nibble method (1985) by three years, so per this wiki's existing flag on Erdős #74 — almost-bipartite graph of infinite chromatic number, the individual gadgets and the amalgamation step are more likely explicit/algebraic (in the style of Kneser graphs, shift graphs, or Zykov/Mycielski-type chromatic-boosting sums — all standard 1970s–80s tools for building high-chromatic graphs with a controlled secondary parameter) than probabilistic in the modern semi-random sense; this is consistent with, but not confirmed as, what [Ro82] actually does.

Portable takeaway for open problems in this cluster. The load-bearing move that generalizes is: *whenever a "make it bipartite/2-colorable by deleting few edges, yet chromatic number is unbounded" question splits into a finite-parametrized sub-case (fixed $k$, fixed $\epsilon$) and an infinite/arbitrarily-slow-$f$ sub-case, look for a single construction schema tunable across both* — solving the easier finite-parametrized version first (as Gallai/Lovász did for the sibling critical-graph problem, and as Rödl's own $\epsilon n$ graph result does relative to his own full hypergraph result) is the natural stepping stone, and the extra "slack" available in a hypergraph's coloring notion (property B, not literal 2-colorability-as-bipartiteness) is what let Rödl close the *infinite*, *arbitrary-$f$* version there but not (yet) for graphs. Any attempted resolution of the still-open Erdős #74 — almost-bipartite graph of infinite chromatic number graph case should therefore look for what *additional* design freedom a hypergraph gadget had that a graph gadget structurally cannot — that is the technical wall the open problem sits behind.

Related

- Erdős #74 — almost-bipartite graph of infinite chromatic number — the general, still-open graph-case problem this hypergraph result is the closest known progress toward; Rödl's hypergraph solution and his linear graph sub-case are both recorded as remarks on that page, and this page is the technique-focused expansion of that remark. - erdos/1092 — the sibling disproved finite/linear statement ($f_r(n)\gg n$ conjectured, false — Rödl's same-paper construction gives $f_r(n)=o(n)$ for every fixed $r\ge2$); the graph-side, fixed-$(\epsilon,k)$ special case of the same underlying construction. - erdos/744 — a different, later (1985) disproof by Rödl & Tuza of a thematically-adjacent EHS82 conjecture about *critical* $k$-chromatic graphs ($f_k(n)$ is eventually *constant*, $\binom{k-1}2$, not $\to\infty$); not the same paper as [Ro82] — flagged here specifically to prevent conflation — but its Gallai/Lovász explicit-construction precursors are the best-documented technique analogs available for reconstructing what [Ro82]'s own gadgets might look like. - Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$ — the $\aleph_1$-chromatic contrast case, open, where even $f(n)\gg n$ fails structurally (disjoint odd cycles) — sets the outer boundary ($\chi<\aleph_1$ is necessary) within which Rödl's countable-chromatic hypergraph construction, and any future graph-case resolution, must live. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — a different, later (1985+) technique by the same author; explicitly *not* what [Ro82]'s 1982 nearly-bipartite construction uses (timing alone rules it out), included here only to pre-empt the natural mis-association. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the 1959 Erdős probabilistic "build almost-good, then locally repair" template; the closest same-shape technique ("high chromatic number surviving a targeted, sparse repair") already documented in this wiki, and the natural first thing to try transplanting toward closing the still-open graph case of Erdős #74 — almost-bipartite graph of infinite chromatic number. - Erdős–Hajnal shift graphs (explicit high-chromatic, controlled-odd-girth construction) — standard explicit unbounded-chromatic building block from the same Erdős–Hajnal school; a candidate ingredient for reconstructing or improving on Rödl's gadgets. - Minimum edge-deletion to bipartite: β(G)/h_G(n), the Max-Cut complement, and the Edwards–Erdős bound — the general $h_G(n)$ / "minimum edges to delete to bipartite-ify" parameter this entire problem cluster (erdos/74, erdos/111, erdos/744, erdos/1092, and this page) is built around; the hypergraph version used here substitutes "2-colorable / property B" for "bipartite."