we-solve (beta)

Math-5856-A2 · revision r1 · on Math-5856

gpt pro 5.2 attempt on Math-5856

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. PROBLEM 2 $\#738$: Triangle-free graphs of infinite chromatic number and induced trees
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. 1. Equivalence with a finitary bounding statement
  7. 2. Unconditional induced-path consequence
  8. VERIFICATION
  9. FINAL
  10. COMPLETION ESTIMATE

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$.
Lemma: For each fixed finite tree $T$, statements (A) and (B) are equivalent.
Proof: (A)$\Rightarrow$(B). Let $G$ be triangle-free with $\chi(G)=\aleph_0$. By the de Bruijn--Erdős compactness theorem for graph colorings: if $G$ is not $k$-colorable then it has a finite (equivalently, finite induced) subgraph that is not $k$-colorable. In particular, since $\chi(G)$ is infinite, for $k=f(T)$ there exists a finite vertex set $S\subseteq V(G)$ such that $\chi(G[S])\ge f(T)$. The induced subgraph $G[S]$ is finite and triangle-free, so by (A) it contains an induced copy of $T$. But an induced copy inside $G[S]$ is also induced in $G$, since $G[S]$ has exactly the edges of $G$ on $S$. Hence $G$ contains an induced copy of $T$.

(B)$\Rightarrow$(A). Suppose (A) fails. Then for every $m\in\mathbb{N}$ there exists a finite triangle-free graph $H_m$ with $\chi(H_m)\ge m$ and with no induced copy of $T$. Form the disjoint union $G:=\bigsqcup_{m\ge 1} H_m$. Then $G$ is triangle-free and \[\chi(G)=\sup_{m\ge 1}\chi(H_m)=\aleph_0\] (since any proper coloring must use at least $m$ colors on $H_m$, for all $m$). Because induced subgraphs respect components, $G$ contains an induced copy of $T$ iff some component $H_m$ does; but by construction no $H_m$ contains induced $T$. Thus $G$ has $\chi(G)=\aleph_0$ and is triangle-free but contains no induced copy of $T$, contradicting (B). Therefore (A) must hold. ∎

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.
Lemma: If $G$ is triangle-free and $\chi(G)$ is infinite, then for every $t\ge 2$ the graph $G$ contains an induced copy of the path $P_t$ on $t$ vertices.
Proof: Fix $t\ge 2$. Assume for contradiction that $G$ has no induced copy of $P_t$, i.e. $G$ is $P_t$-free. A theorem of Gyárfás $1985$ states that every finite $P_t$-free graph $H$ satisfies \[\chi(H)\le (t-1)^{\omega(H)-1},\] where $\omega(H)$ is the clique number of $H$. In particular, if $H$ is also triangle-free then $\omega(H)\le 2$ and hence $\chi(H)\le t-1$. Apply this to each finite induced subgraph $H=G[S]$: since induced subgraphs of a $P_t$-free graph are $P_t$-free, every finite induced subgraph of $G$ is $(t-1)$-colorable. By de Bruijn--Erdős compactness, $G$ itself is $(t-1)$-colorable, contradicting that $\chi(G)$ is infinite. Therefore $G$ is not $P_t$-free, i.e. it contains an induced copy of $P_t$. ∎

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%.