There is an uncountable-chromatic graph \(G\) so that the size of the smallest \(n\)-chromatic subgraph grows arbitrarily slowly

A problem on \( \aleph_1\)-chromatic graphs (proposed by Erdös, Hajnal and Szemerédi [1])
Is it true that for any \( f(n)\), there is an \( \aleph_1\)-chromatic graph \( G\) so that if \( g(n)\) is the smallest integer for which \( G\) has an \( n\)-chromatic subgraph of \( g(n)\) vertices, then \( f(n)/g(n) \rightarrow 0\)?

Taylor [2] [3] stated the conjecture that if \( G\) is an uncountably chromatic graph then there are arbitrarily large chromatic graphs \( H\) such that every finite subgraph of \( H\) is already a subgraph of \( G\). It is clear that there must be a cardinal \( \lambda\) with the property that if for some family \( {{\mathcal K}}\) of finite graphs, there is a graph with chromatic number at least \( \lambda\) and containing finite subgraphs from \( {{\mathcal K}}\) then there must be similar graphs of arbitrarily high chromatic number.

Erdös, Hajnal and Shelah [4] strengthened the conjecture by actually guessing what the obligatory classes of finite subgraphs could be. They conjectured that every uncountably chromatic graph contains all finite subgraphs of the so-called \( n\)-shift graph for some \( n\). (That is, when we take the \( n\)-element subsets of \( \omega\) as the vertex set and join \( \{x_,\ldots,x_n\}\) to \( \{x_2,\ldots,x_{n+1}\}\)). This rather bold conjecture was refuted by Hajnal and Komjáth [5]. Komjáth and Shelah [6] gave an explicit list of countably many classes \( \{{\mathcal K}_1,\ldots\}\) of finite graphs such that if for some \( \kappa\) , \( \kappa^{\aleph_0}=\kappa\) holds and \( G\) is a graph with chromatic number (and cardinality) \( \kappa^+\), then for some \( n\), \( G\) contains every element of \( {\mathcal K}_n\). And, under GCH, if \( \lambda\) is uncountable regular, then there is a cardinal and cofinality-preserving forcing which adds a \( \lambda\)-chromatic graph on \( \lambda\) which only contains finite subgraphs from \( {\mathcal K}_n\) for some \( n\). This gives a consistent ``yes'' answer for a restricted case of Taylor's conjecture.


Bibliography
1 P. Erdös, A. Hajnal and E. Szemerédi, On almost bipartite large chromatic graphs, Annals of Discrete Math. 12 (1982), Theory and practice of combinatorics, North-Holland Math. Stud., 60, 117-123, North-Holland, Amsterdam, New York, 1982.
2 W. Taylor, Atomic compactness and elementary equivalence, Fund. Math. 71 (1971), 103-112.
3 W. Taylor, Problem 42, Comb. Structures and their applications, Proc. of the Calgary International Conference, 1969.
4 P. Erdös, A. Hajnal, S. Shelah, On some general properties of chromatic number, in: Topics in Topology, Keszthely (Hungary), 1972, Coll. Math. Soc. J. Bolyai 8, 243-255.
5 A. Hajnal and P. Komjáth, What must and what need not be contained in a graph of uncountable chromatic number ? Combinatorica 4 (1984), 47-52.
6 P. Komjáth, S. Shelah: On Taylor's problem, Acta Math. Hung., 70 (1996), 217-225.