Erdős problem #1111 — wave 8f

Access date: 2026-07-28 (UTC).

0. Mandatory live-page gate

I fetched https://www.erdosproblems.com/1111 and its discussion thread through the Bright Data cloud browser, rather than datacenter curl. The browser returned the real problem page (title 1111 | Erdős Problems), not a Cloudflare interstitial.

The live page's statement, verbatim from its “View the LaTeX source” view, is:

If $G$ is a finite graph and $A,B$ are disjoint sets of vertices then we call $A,B$ anticomplete if there are no edges between $A$ and $B$.

If $t,c\geq 1$ then there exists $d\geq 1$ such that if $\chi(G)\geq d$ and $\omega(G)<t$ then there are anticomplete sets $A,B$ with $\chi(A)\geq \chi(B)\geq c$.

Live status and collision markers:

Thus the mandatory stop condition did not fire.

The two live comments were also read:

1. Alfaiz (2025-12-08) points to the tournament reformulation: a high-dichromatic

tournament should contain two high-dichromatic sets with all cross-arcs oriented in one direction. The comment cites Klingelhöfer–Newman and Nguyen–Scott–Seymour.

1. Zach Hunter (2025-12-16) says that “it suffices to check $t\leq c$” is confusing and

observes the elementary monotonicity in $c$.

The site itself warns that comments are unverified. I therefore used neither comment as a theorem; I checked the tournament claim in the primary papers below.

The live page lists the following known results:

• El-Zahar and Erdős reduce to $t\leq c$ and define $d(t,c)$.
• Wagon's result gives

$d(t,2)\leq\binom t2+1$ and $d(t+1,2)\leq d(t,2)+t$.

• The page literally prints

$t(2,2)=2$, $t(3,2)=4$, $t(4,2)=5$; the surrounding definition and the 1985 source show that the intended function symbol is $d$ (called $f$ in that paper).

• El-Zahar and Erdős give $d(3,3)\leq8$ and, for $t>3$,

\[ d(t,3)\leq 2\binom{t-1}{3}+7\binom{t-1}{2}+t. \]

• Nguyen–Scott–Seymour prove a weakening in which $\chi(B)\geq c$ and

$G[A]$ has minimum degree at least $c$.

1. Claim labels

I use the requested labels throughout:

• (a) elementary-rigorous: a complete proof is in this report.
• (b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the

explicitly named published theorem.

• (c) plausible/structural-unverified: not used as a theorem.
• (d) computational-only: established by the supplied exhaustive checker, not promoted

to an unproved uniform assertion.

2. Primary-source literature check

I found no primary source claiming to solve the general problem. The following documents were opened and their actual theorem/conjecture text checked.

1. El-Zahar–Erdős (1985).

Primary PDF, Combinatorica 5 (1985), 295–300. Their Theorem 2 proves $d(3,3)\leq8$. Immediately afterward they state that Mycielski's triangle-free 5-chromatic graph has no two non-neighboring odd circuits, giving $d(3,3)\geq6$. (b)

1. Nguyen–Scott–Seymour (2024).

Author PDF, arXiv:2303.13449, DOI 10.1016/j.jctb.2023.11.004. The paper explicitly says the question remains open and proves the minimum-degree/chromatic-number weakening reported by the live page. (b)

1. Klingelhöfer–Newman (2024).

Author PDF, arXiv:2307.04446, DOI 10.1007/s00493-024-00098-z. Their Conjectures 1.5 and 1.6 are respectively the graph problem and the tournament complete-pair conjecture. Section 4 proves their equivalence using the paper's arc-local-to-global theorem for dense digraphs. (b)

1. Nguyen–Scott–Seymour (2025).

Author PDF, arXiv:2306.02364, DOI 10.1016/j.jctb.2025.02.002. The revised paper records the equivalence and gives a second proof. Its tournament Conjecture 1.2 is exactly the reformulation described in the live comment. (b)

1. Grinstead–Katinsky–Van Stone (1989).

Primary PDF, J. Combin. Math. Combin. Comput. 6 (1989), 189–193. Page 193 prints an adjacency list for a 22-vertex triangle-free 5-chromatic graph. I transcribed and independently checked this particular graph below. (d)

1. Jensen–Royle (1995).

Publisher record and abstract, DOI 10.1002/jgt.3190190111. Their exhaustive computer search proves that 22 is the minimum order of a triangle-free 5-chromatic graph. (b)

1. 2025 Barbados open-problem notes.

Primary workshop notes, Problem 11, still present the triangle-free case as open. The notes contain an informal triangle-free-process argument against a much stronger linear version and announce an $\Omega(t^{4/3})$ lower-bound heuristic. The discussion immediately flags that the required pseudorandom estimates are nontrivial. I classify that workshop argument as (c), not as a proved update to #1111.

Exact-title, exact-conjecture, and 2025–2026 searches found related work on anticomplete pairs and treewidth, but no later primary paper claiming a proof or disproof of #1111. This is a literature-search miss, not a claim that no such paper can exist.

3. The concrete core $(t,c)=(3,3)$

For a triangle-free graph, a vertex set has chromatic number at least three exactly when its induced graph is non-bipartite, equivalently when it contains an odd cycle. Therefore:

A triangle-free graph has anticomplete sets $A,B$ with $\chi(A),\chi(B)\geq3$ if and only if it has two anticomplete odd cycles.

Indeed, take one odd cycle from each non-bipartite induced graph in one direction, and take the two cycle vertex sets in the other. (a)

Thus $d(3,3)-1$ is the largest possible chromatic number of a triangle-free graph with no two anticomplete odd cycles. The 1985 bounds and the explicit witness below give

The exact value is not asserted here.

4. A self-contained odd-girth reduction

Theorem

Let $G$ be triangle-free and suppose that $G$ has no two anticomplete odd cycles. Let $g$ be the length of a shortest odd cycle of $G$. Then

This is (a). I did not find this stratified statement in the primary sources searched; the proof is included in full rather than relying on novelty.

Proof

If $G$ is bipartite there is nothing to prove, so choose a shortest odd cycle

Indices below are modulo $g$. Put

The graph $G[R]$ is bipartite: otherwise it contains an odd cycle anticomplete to $C$.

We first record the possible neighbourhood of a vertex $x\in X$ on $C$. Two $C$-neighbours of $x$ split $C$ into paths of lengths $p$ and $g-p$. Exactly one path has odd length. Adding $x$ to that path gives an odd cycle, so shortestness of $C$ forces its path length to be at least $g-2$. The other path consequently has length at most two; triangle-freeness rules out length one. Hence any two $C$-neighbours of $x$ are at cyclic distance exactly two. There cannot be three of them. Every $x\in X$ therefore has one of the following types:

Now let adjacent $x,y\in X$ have types with $C$-neighbour sets $P,Q$. For $a\in P,b\in Q$, the two $a$–$b$ paths on $C$, together with $a x y b$, give cycles whose lengths are the two path lengths plus three. The even one of the two path lengths therefore gives an odd cycle. Shortestness of $C$ forces that even path to have length at least $g-3$, so the other path has length one or three. Thus every $a\in P,b\in Q$ differs cyclically by $\pm1$ or $\pm3$.

It follows by a direct modular check that every edge of $G[X]$ maps to an edge of the following type graph $F_g$:

Vertices of the same type are nonadjacent because they share a neighbour on $C$. Consequently the type map is a graph homomorphism $G[X]\to F_g$.

We now colour $F_g$. Choose a cyclic word $a_0a_1\ldots a_{g-1}$ in which symbols at cyclic distance one or three are different:

The first two rows are checked directly. For the third, the alternating portion is proper at every odd distance; the only remaining distance-one and distance-three pairs lie in or cross the fixed suffix/junction and are read off directly. (For $g=9$ the word is 010121202; for $g\geq11$ the two junctions have the same fixed local pattern.)

Give type $D_i$ colour $a_i$ and type $S_i$ colour $a_{i+1}$. Formula (3) and the distance-one/distance-three property show:

• $D_iD_{i\pm1}$ receive $a_i,a_{i\pm1}$;
• $S_iS_{i\pm1}$ and $S_iS_{i\pm3}$ receive symbols at distance one or three;
• $S_iD_i,S_iD_{i+2},S_iD_{i-2}$ receive symbols at distance one, one, and three.

Hence this is a proper $q$-colouring of $F_g$, and therefore of $G[X]$.

Finally colour $v_0$ with $a_0$. Colour the path $v_1,\ldots,v_{g-1}$ alternately with two new colours $q,q+1$, and use those same two new colours on the bipartite graph $G[R]$. This is valid because $R$ is anticomplete to $C$. Use the type colouring on $X$. The only colour shared by $X$ and $C$ is $a_0$. The types containing $v_0$ are $S_0,D_1,D_{g-1}$, with colours $a_1,a_1,a_{g-1}$ respectively, all different from $a_0$. The palette on $X$ is disjoint from the two colours on $R$. Thus all edges are properly coloured with $q+2$ colours, giving (1). ∎

The type-palette counts themselves cannot be improved while retaining only the coarse type graph:

• for $g=5$, the $S$-types induce $K_5$;
• for $g=7$, the complement of the graph on the seven $S$-types is a 7-cycle, so every

stable set has size at most two and four colours are necessary;

• for odd $g\geq9$, the $D$-types induce an odd cycle, so three colours are necessary.

These observations are (a) and explain exactly where a type-only argument loses information.

Consequences

1. To improve the classical $d(3,3)\leq8$ to $d(3,3)\leq7$, it now suffices to prove:

> Every triangle-free graph of odd girth five with no two anticomplete odd cycles is > 6-colourable.

The $g=7$ case is already 6-colourable by (1), and $g\geq9$ is 5-colourable. (a)

1. To prove the exact value $d(3,3)=6$, it suffices to prove 5-colourability in the two

remaining odd-girth cases $g=5$ and $g=7$. (a)

This is a clean reduction, not a solution of either remaining case.

5. Exact 22-vertex lower-bound witness

The following is the adjacency list printed by Grinstead–Katinsky–Van Stone. It is included here so the result does not depend on a drawing or an opaque database identifier.

 1:  2 5 9 10 17 19 20 22
 2:  1 3 11 12 14 15
 3:  2 4 8 9 18 19 21 22
 4:  3 5 10 11 14 17 20
 5:  1 4 8 12 15 18 21
 6:  11 12 14 15 17 18 19
 7:  8 9 10 11 12 17 18 19
 8:  3 5 7 14 16 20
 9:  1 3 7 14 15 16
10:  1 4 7 15 16 21
11:  2 4 6 7 16 21 22
12:  2 5 6 7 16 20 22
13:  14 15 16 17 18 19 20 21 22
14:  2 4 6 8 9 13
15:  2 5 6 9 10 13
16:  8 9 10 11 12 13
17:  1 4 6 7 13
18:  3 5 6 7 13
19:  1 3 6 7 13
20:  1 4 8 12 13
21:  3 5 10 11 13
22:  1 3 11 12 13

Portable labelled graph6 encoding:

Uhc?@UacakHo??TWheOB{d__mADKCCaK?gY?gB_?

The standalone checker establishes the following from scratch:

• 22 vertices and 70 edges;
• no triangle;
• no 4-colouring (787 nodes in a symmetry-reduced exhaustive DSATUR tree);
• the explicit proper 5-colouring, in vertex order 1 through 22,

\[ (0,3,1,0,1,0,0,2,3,3,2,2,0,1,2,1,1,2,2,1,4,3); \]

• exactly 666 chordless odd-cycle vertex sets, obtained independently both by scanning all

$2^{22}$ subsets and by a canonical chordless-cycle DFS;

• the anti-neighbourhood of every one of those 666 cycles is bipartite.

Every odd cycle contains a chordless odd cycle. Therefore, if two odd cycles were anticomplete, chordless odd cycles inside them would also be anticomplete. The last check is consequently exhaustive, not a bounded-cycle-length heuristic. Hence this graph has no two anticomplete odd cycles. (d)

It follows computationally that this graph witnesses $d(3,3)\geq6$. It improves the order of the 23-vertex Mycielski witness cited in 1985, without improving the numerical lower bound. (d)

Moreover, it is a minimum-order witness for this numerical lower bound, modulo Jensen–Royle's theorem that every triangle-free 5-chromatic graph has at least 22 vertices. Any triangle-free graph of chromatic number at least five contains a 5-chromatic subgraph: delete edges one at a time, noting that one edge deletion lowers chromatic number by at most one, until the value first reaches five. (b), using Jensen–Royle

6. Reproduction

The checker is:

runs/erdos1111_wave8f_reverify.py

Run:

python3 runs/erdos1111_wave8f_reverify.py

It uses only the Python standard library. On this VM it completed in under 20 seconds and printed:

22-vertex witness:
  vertices=22 edges=70
  triangle_free=yes
  4_colourable=no (exhaustive DSATUR nodes=787); 5_colourable=yes (nodes=23)
  5-colouring (vertices 1..22): 0 3 1 0 1 0 0 2 3 3 2 2 0 1 2 1 1 2 2 1 4 3
  chordless_odd_cycles=666 (two methods agree)
  anticomplete_odd_cycle_pair=no
  graph6=Uhc?@UacakHo??TWheOB{d__mADKCCaK?gY?gB_?
  labelled-edge-sha256=26761282734affd1d81fd5dcab5496f4b9852b69443051eccdd746f2945f285f
Odd-girth type lemma:
  proper uniform word/type colourings checked for every odd 5<=g<=501
  type compatibility independently reconstructed by shortest-odd-cycle search for every odd 5<=g<=31
  resulting no-pair chromatic bounds:
    g=5 -> 7 colours
    g=7 -> 6 colours
    odd g>=9 -> 5 colours
ALL CHECKS PASSED

The finite tests through $g=501$ are regression checks only. Uniformity in $g$ comes from the displayed word and proof in Section 4, not from extrapolating a finite list.

7. Exact remaining wall

The general problem remains open, as does the exact value of $d(3,3)$.

For the smallest unresolved parameter pair, the missing statements are now sharply isolated:

• A 6-colour theorem for the $C_5$-layer case would improve $d(3,3)\leq8$ to

$d(3,3)\leq7$.

• A 5-colour theorem for both the $C_5$- and $C_7$-layer cases would combine with the

22-vertex witness to prove $d(3,3)=6$.

The exact obstruction to the elementary type method is also visible: its type graphs genuinely need five colours for $g=5$ and four for $g=7$, even though an actual $G[X]$ is triangle-free and need not contain all allowed type edges. Progress must exploit those missing-edge constraints, the no-anticomplete-odd-cycles condition inside the type classes, or a finer state than the $C$-neighbour type. Merely recolouring the coarse type graph cannot improve (1).

A global brute-force search is not a credible few-minute computation: even the minimum order of a triangle-free 6-chromatic graph is a substantially harder extremal enumeration than the 22-vertex check above. I did not run such a search and make no computational extrapolation from the witness.

PARTIAL: Proved the self-contained no-pair bounds chi<=7,6,5 for odd girth 5,7,>=9, reducing any d(3,3)<=7 improvement to the C5-layer case; also verified a minimum-order 22-vertex witness for d(3,3)>=6.