Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a graph with chromatic number . Is there, for every cardinal number , some graph of chromatic number such that every finite subgraph of is a subgraph of ?
Source: erdosproblems.com/736
No claim settles this problem.
Open. The site labels the problem NOT PROVABLE, since Komjáth and Shelah [KoSh05] proved it consistent with ZFC that the answer is no, through a graph of chromatic number such that every graph whose finite subgraphs all occur in it has chromatic number at most , so that no exists for . That result settles one side: ZFC does not prove a positive answer. Whether a positive answer is itself consistent, and so whether ZFC also fails to disprove it, is not settled. This page departs from the site's label and shows the problem open, because one side alone leaves the question open. The question is Walter Taylor's conjecture at ; the general form replaces by any uncountable cardinal , and Erdős asked more broadly which families of finite graphs contain all the finite subgraphs of some graph of chromatic number .