Problem #738: If $G$ has infinite chromatic number and is triangle-free...

If $G$ has infinite chromatic number and is triangle-free (contains no $K_3$) then must $G$ contain every tree as an induced subgraph?

SOLVED

Problem Statement

If $G$ has infinite chromatic number and is triangle-free (contains no $K_3$) then must $G$ contain every tree as an induced subgraph?

Categories: Graph Theory Chromatic Number

A conjecture of Gyárfás.

Source: erdosproblems.com/738 | Last verified: January 16, 2026