### Finite subgraphs of uncountably chromatic graphs

by Komjath and Shelah. [KoSh:788]

J Graph Theory., 2005

It is consistent that for every monotonically increasing
function f: omega-> omega there is a graph with size and
chromatic number aleph_1 in which every n-chromatic subgraph
has at least f(n) elements (n >= 3).
This solves a textdollar ~250 problem of Erdos.
It is also consistent that there is a graph
X with Chr (X)=|X|= aleph_1 such that if Y is a graph all
whose finite subgraphs occur in X then Chr (Y) <=
aleph_2 .

Back to the list of publications