Erdős Problem #738

Erdős problems #655, #738, #740 --- Round 2 continuation

Problem #738

1) ROUND-2 OBJECTIVE

Path (C): keep the full problem open, but convert the Round-1 reduction into genuine new positive theorems for large classes of trees, and isolate a sharper obstruction for any future counterexample.

This is the most promising direction because Round 1 already showed that the full problem is equivalent to a finite forcing statement, so the natural next step is to import the strongest finite theorems that are already known and lift them to the infinite triangle-free setting.

2) Round-1 FOUNDATION USED

I use the following vetted Round-1 ingredients.

• Finite-to-infinite compactness principle. If a finite-tree forcing theorem holds for all sufficiently large finite triangle-free graphs, then the corresponding statement holds for every triangle-free graph of infinite chromatic number.
• Induced-path consequence. Every triangle-free graph of infinite chromatic number contains induced paths of all finite lengths.

I do not re-prove these Round-1 facts.

3) NEW INSIGHT / TOOL (ROUND-2)

Three finite theorems can now be fed through the Round-1 compactness mechanism.

1. Scott's induced-subdivision theorem: every bounded-clique graph of sufficiently large chromatic number contains an induced subdivision of any fixed tree [Scott97].
2. Scott's corollary for subdivisions of stars: if $T$ is a subdivision of a star, then $\operatorname{Forb}(T)$ is $\chi$-bounded [Scott97].
3. Nguyen--Scott--Seymour's path-induced theorem: every bounded-clique graph of sufficiently large chromatic number contains a path-induced copy of any fixed rooted tree [NguyenScottSeymour24].

This yields new infinite-chromatic consequences that were not extracted in Round 1.

4) ATTACK PLAN (ROUND-2)

After Round 1, the exact gap was: which nontrivial families of trees can already be forced in the infinite triangle-free setting?

I will prove four new claims.

1. Every finite tree occurs as an induced subdivision.
2. Every finite subdivision of a star occurs as an induced subgraph.
3. Every finite tree of radius at most $2$ occurs as an induced subgraph.
4. Every finite rooted tree occurs as a path-induced subgraph.

These claims together isolate the first genuinely open family: a possible counterexample tree must lie outside both the radius-$2$ family and the subdivision-of-a-star family, and any negative example must exploit the gap between induced copies and path-induced / induced-subdivision copies.

5) WORK (ROUND-2)

We write $\chi(G)$ for the chromatic number and say that $G$ is triangle-free if it contains no $K_3$.

Claim 1.

Every triangle-free graph of infinite chromatic number contains an induced subdivision of every finite tree.

Proof.

Fix a finite tree $T$ and let $G$ be triangle-free with infinite chromatic number. By Scott's theorem [Scott97, Theorem 3], for $k=3$ there exists an integer $c(T)$ such that every finite graph $H$ with $\chi(H)\ge c(T)$ either contains $K_3$ or contains an induced subdivision of $T$.

Since $\chi(G)$ is infinite, the de Bruijn--Erdős compactness theorem gives a finite induced subgraph $G[S]$ with $\chi(G[S])\ge c(T)$. Because $G$ is triangle-free, so is $G[S]$; hence $G[S]$ cannot contain $K_3$. Therefore $G[S]$ contains an induced subdivision of $T$. Since $G[S]$ is induced, that subdivision is also induced in $G$.

So every finite tree appears in $G$ as an induced subdivision. $\square$

Claim 2.

Every triangle-free graph of infinite chromatic number contains every finite subdivision of a star as an induced subgraph.

Proof.

Let $T$ be a subdivision of a star. Scott proved that $\operatorname{Forb}(T)$ is $\chi$-bounded [Scott97, Corollary 2]. Thus there exists a finite number $b(T)$ such that every triangle-free $T$-free graph has chromatic number at most $b(T)$.

Now let $G$ be triangle-free with infinite chromatic number. Choose a finite induced subgraph $G[S]$ with $\chi(G[S])>b(T)$. Then $G[S]$ cannot be $T$-free, so it contains an induced copy of $T$. Since $G[S]$ is induced, this copy is induced in $G$ as well. $\square$

Claim 3.

Every triangle-free graph of infinite chromatic number contains every finite tree of radius at most $2$ as an induced subgraph.

Proof.

Let $T$ be a tree of radius at most $2$. Scott records the theorem of Gyárfás, Szemerédi, and Tuza that for every such $T$ there exists a constant $c(T)$ such that every triangle-free finite graph of chromatic number at least $c(T)$ contains an induced copy of $T$; he also records the stronger theorem of Kierstead and Penrice that $\operatorname{Forb}(T)$ is $\chi$-bounded for every radius-$2$ tree [Scott97, p. 2, Theorem B].

Applying the Round-1 compactness principle exactly as above, any triangle-free graph $G$ with infinite chromatic number has a finite induced subgraph of chromatic number at least $c(T)$, and hence contains an induced copy of $T$. $\square$

Claim 4.

Every triangle-free graph of infinite chromatic number contains a path-induced copy of every finite rooted tree.

Proof.

Fix a finite rooted tree $(T,r)$ and let $G$ be triangle-free with infinite chromatic number. Nguyen, Scott, and Seymour proved that for every rooted tree $(T,r)$ and every integer $t\ge 1$, every graph with no clique of size $t$ and sufficiently large chromatic number admits a path-induced copy of $(T,r)$ [NguyenScottSeymour24, Theorem 1.2 and Theorem 2.3].

Set $t=3$. Then there exists $p(T,r)$ such that every finite graph $H$ with no $K_3$ and $\chi(H)\ge p(T,r)$ admits a path-induced copy of $(T,r)$. Again choose a finite induced subgraph $G[S]$ with $\chi(G[S])\ge p(T,r)$. Since $G[S]$ is triangle-free, it contains a path-induced copy of $(T,r)$, and because $G[S]$ is induced, that same copy is path-induced in $G$. Thus every finite rooted tree occurs path-induced in $G$. $\square$

Sharper obstruction extracted from Claims 1--4.

Suppose the original Problem #738 were false. Then there would exist a finite tree $T$ and a triangle-free graph $G$ of infinite chromatic number such that $G$ contains no induced copy of $T$. Claims 2 and 3 show that such a tree $T$ cannot be a subdivision of a star and cannot have radius at most $2$. Therefore any minimal unresolved tree must have radius at least $3$ and at least two vertices of degree greater than $2$.

Moreover Claim 4 shows that $G$ still contains a path-induced copy of every rooted version of $T$, and Claim 1 shows that it contains an induced subdivision of $T$. So any future counterexample must exploit the difference between an induced copy of $T$ and the weaker structures "induced subdivision of $T$" and "path-induced copy of $(T,r)$".

6) ADVERSARIAL VERIFICATION

• Persistence from finite induced subgraphs. Every copy found inside $G[S]$ remains induced (or path-induced) in $G$ because $G[S]$ has exactly the edges of $G$ on $S$.
• Triangle-free hypothesis. In Claims 1--4, the finite theorems are applied with clique bound $2$, equivalently with forbidden clique $K_3$. This matches the hypothesis exactly.
• Why path-induced is genuinely weaker than induced. Consider the five-vertex tree with edges $ra, rb, ax, by$, rooted at $r$. Add one extra edge $xy$. The resulting graph is still triangle-free. The original tree appears as a path-induced rooted subgraph (both root-to-leaf paths $r$--$a$--$x$ and $r$--$b$--$y$ are induced), but it is not an induced subgraph because of the extra edge $xy$. So Claim 4 does not already settle the original problem.
• Why induced subdivisions do not settle the original problem. An induced subdivision of $T$ may insert extra degree-$2$ vertices on edges of $T$; that need not give an induced copy of $T$ itself. Thus Claim 1 is strictly weaker than the target statement for general $T$.
• Boundary of the new positive families. Claims 2 and 3 are incomparable families: radius-$2$ trees may have many branching vertices, whereas subdivisions of stars have at most one branching vertex. So together they strictly enlarge the known forced family.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

Round 2 proves substantially more than Round 1:

1. every finite tree appears as an induced subdivision;
2. every finite subdivision of a star appears as an induced subgraph;
3. every finite radius-$2$ tree appears as an induced subgraph;
4. every finite rooted tree appears as a path-induced subgraph.

So the first genuinely open trees are those of radius at least $3$ with at least two branching vertices, and any counterexample must separate induced copies from induced subdivisions / path-induced copies. The full problem remains open [Bloom738].

8) COMPLETION ESTIMATE

COMPLETION: 60%

9) REFERENCES

References used in Round 2 are listed in the global bibliography below.

References

References

• [Bloom738] T. F. Bloom (ed.), Erdős Problem #738, Erdős Problems Project, accessed 8 March 2026.
• [Bloom740] T. F. Bloom (ed.), Erdős Problem #740, Erdős Problems Project, accessed 8 March 2026.
• [Scott97] A. D. Scott, Induced trees in graphs of large chromatic number, Journal of Graph Theory 24 $1997$, 297--311.
• [NguyenScottSeymour24] T. Nguyen, A. Scott, and P. Seymour, A note on the Gyárfás--Sumner conjecture, Graphs and Combinatorics 40 $2024$, Article 33.
• [Rodl77] V. Rödl, On the chromatic number of subgraphs of a given graph, Proceedings of the American Mathematical Society 64 $1977$, 370--371.
• [KomjathShelah88] P. Komjáth and S. Shelah, Forcing constructions for uncountably chromatic graphs, Journal of Symbolic Logic 53 $1988$, 696--707.

Erdős Problem #738: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

Does every triangle-free graph of infinite chromatic number contain every finite tree as an induced subgraph?

All supplied versions considered: 738.tex. The source transfers known finite theorems about radius-two trees, subdivided stars, induced subdivisions and path-induced copies. Those are literature consequences, not a solution for all trees. I isolate a sufficient cycle exclusion that makes an elementary embedding argument work, and explain precisely why triangle-freeness alone does not supply it.

2) WORK

A direct high-girth case.

Let $T$ have $t\ge2$ vertices and diameter $d$. Every finite graph $G$ with $\chi(G)\ge t$ and girth greater than $d+1$ contains an induced copy of $T$.

First, $G$ has a nonempty subgraph of minimum degree at least $t-1$. Otherwise successively deleting a vertex of degree at most $t-2$ and coloring in reverse order would give a $(t-1)$-coloring. Root $T$ and embed it greedily in this subgraph, parents before children. When inserting a child, at most $t-2$ already used vertices other than its parent can block neighbors of the parent. Minimum degree $t-1$ therefore leaves an unused neighbor. This produces an ordinary copy of $T$.

Any additional ambient edge between two nonadjacent vertices of this copy, at tree distance $s$, would create a cycle of length $s+1\le d+1$. The girth hypothesis excludes every such edge, so the copy is induced. By the finite-coloring compactness theorem the same conclusion holds when $G$ has infinite chromatic number and that girth condition.

More precisely it suffices to exclude the lengths $\{d_T(u,v)+1:u,v\text{ nonadjacent in }T\}$, rather than all short cycles. Triangle-freeness excludes only the distance-two chords. Chords between vertices at distance three create four-cycles, which are entirely compatible with triangle-freeness. Removing ambient edges to obtain a high-girth subgraph does not repair this, since inducedness must be measured in the original graph.

3) ADVERSARIAL VERIFICATION

The greedy proof is for a finite tree and an ordinary subgraph, followed by a separate ambient-chord check. It is not valid to confuse a subdivision with the original tree or to transfer inducedness from an arbitrary edge-deleted subgraph. The additional girth assumption is explicitly stronger than the target.

4) FINAL

UNRESOLVED. An argument ruling out the longer-distance chords using only triangle-freeness and large chromatic number is still missing. This is a verified special case and an identified obstruction, not an extension of the known general tree families.

5) SOURCES CHECKED

Full supplied source read. Checked Nguyen--Scott--Seymour, https://arxiv.org/abs/2302.08922, on 2026-09-23; its abstract states the path-induced conclusion and retains the full induced-tree question as open. No stronger statement is attributed to it.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 8%

PROBLEM 2 $\#738$: Triangle-free graphs of infinite chromatic number and induced trees

FORMAL RESTATEMENT

Let $G=(V,E)$ be a (simple, undirected) graph.

• $\chi(G)$ denotes the chromatic number of $G$.
• "$G$ is triangle-free" means $G$ contains no $K_3$ as a (not necessarily induced) subgraph.
• For a graph $H$, we say $H$ is an induced subgraph of $G$ if there is a vertex set $S\subseteq V$ such that $H\cong G[S]$, the subgraph induced by $S$.
• Ambiguity: "tree" can mean finite or infinite. In the context of Gyárfás' induced-subtree conjecture, the intended meaning is finite tree. We adopt:

  A tree $T$ is a finite, connected, acyclic graph.

Question (interpreting "tree" as finite):

If $\chi(G)$ is infinite and $G$ is triangle-free, must it be that for every finite tree $T$ there exists an induced subgraph of $G$ isomorphic to $T$?

QUICK LITERATURE/CONTEXT CHECK

The problem is listed as Erdős Problem #738 and marked open in the online Erdős Problems Project. It is described there as a conjecture of Gyárfás. This is closely related to the (finite) Gyárfás--Sumner conjecture, which asserts (roughly) that graphs of sufficiently large chromatic number and bounded clique number must contain any fixed tree as an induced subgraph. Many partial results are known (e.g. for trees of radius $2$, certain radius-$3$ trees, subdivided stars, caterpillars/chandeliers, etc.), but the general case remains open.

ATTACK PLAN

1. Proof-track idea: reduce the infinite statement to a finitary bound "triangle-free and $T$-free $\Rightarrow$ bounded chromatic number", and then try to invoke known cases.
2. Disproof-track idea: attempt to construct a triangle-free graph with $\chi(G)=\aleph_0$ (or larger) that avoids an induced copy of some fixed tree $T$.
3. Best path here: prove clean equivalences and strongest unconditional consequences currently accessible (e.g. existence of induced paths of all finite lengths), and clearly identify the remaining gap.

WORK

1. Equivalence with a finitary bounding statement

For a fixed finite tree $T$, consider:

• (A) There exists $f(T)\in\mathbb{N}$ such that every finite triangle-free graph $H$ with $\chi(H)\ge f(T)$ contains an induced copy of $T$.
• (B) Every triangle-free graph $G$ with $\chi(G)=\aleph_0$ contains an induced copy of $T$.

Conclusion. The original question for $\chi(G)=\aleph_0$ is essentially equivalent (tree-by-tree) to the finitary Gyárfás induced-subtree conjecture restricted to triangle-free graphs. The same equivalence can be adapted to larger infinite cardinals if one formulates the appropriate finitary/uniform bounding statements.

2. Unconditional induced-path consequence

Even without resolving the full conjecture for all trees, one can show that triangle-free graphs of infinite chromatic number must contain induced paths of all finite lengths.

VERIFICATION

• The equivalence proof carefully uses that an induced copy found inside a finite induced subgraph $G[S]$ remains induced in $G$.
• In the disjoint-union direction, induced copies cannot mix vertices from different components, so "$T$-free" is preserved.
• The induced-path lemma relies on (i) Gyárfás' explicit $\chi$-bound for $P_t$-free graphs, (ii) triangle-free implies $\omega\le 2$, and (iii) de Bruijn--Erdős compactness.

FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. For each fixed finite tree $T$, the statement

"every triangle-free graph with $\chi=\aleph_0$ contains an induced copy of $T$"

is equivalent to the finitary existence of a bound $f(T)$ forcing an induced copy of $T$ in every finite triangle-free graph of chromatic number at least $f(T)$. Also, every triangle-free graph of infinite chromatic number contains induced paths $P_t$ for all finite $t$.

(ii) First gap. Proving the existence of such a finite bound $f(T)$ for every finite tree $T$ (beyond known families such as radius-$2$ trees, certain caterpillars/chandeliers, etc.) is exactly the missing step.

(iii) Top 3 next moves.

1. Extend known "controlled graph"/structural methods (e.g. Scott--Seymour program on induced subgraphs of large chromatic number) to larger families of trees.
2. Focus on minimal counterexamples: analyze triangle-free $T$-free graphs of large chromatic number for unavoidable induced configurations (long induced paths, radius constraints, decompositions).
3. Explore whether additional hypotheses (bounded maximum degree, forbidden induced cycles/holes, etc.) yield full induced-tree universality, to build intuition or attack special cases.

(iv) What a minimal counterexample would likely look like. A counterexample for a particular finite tree $T$ would have to be a triangle-free graph $G$ with $\chi(G)=\aleph_0$ (or larger) that is $T$-free as an induced subgraph. By the induced-path lemma above, such a graph must still contain induced paths of all lengths, so $T$ would need branching structure not forced by long induced paths alone.

COMPLETION ESTIMATE

COMPLETION: 35%.