# Sh:788

• Komjáth, P., & Shelah, S. (2005). Finite subgraphs of uncountably chromatic graphs. J. Graph Theory, 49(1), 28–38.
• Abstract:
It is consistent that for every monotonically increasing function f:\omega\to\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\geq 3). This solves a  250 problem of Erdős. It is also consistent that there is a graph X with {\rm Chr}(X)=|X|=\aleph_1 such that if Y is a graph all whose finite subgraphs occur in X then {\rm Chr}(Y)\leq \aleph_2.
• Version 2002-05-24_11 (11p) published version (11p)
Bib entry
@article{Sh:788,
author = {Komj{\'a}th, P{\'e}ter and Shelah, Saharon},
title = {{Finite subgraphs of uncountably chromatic graphs}},
journal = {J. Graph Theory},
fjournal = {Journal of Graph Theory},
volume = {49},
number = {1},
year = {2005},
pages = {28--38},
issn = {0364-9024},
mrnumber = {2130468},
mrclass = {05C15 (03E05 03E35)},
doi = {10.1002/jgt.20060},
note = {\href{https://arxiv.org/abs/math/0212064}{arXiv: math/0212064}},
arxiv_number = {math/0212064}
}