Finite subgraphs of uncountably chromatic graphs
Finite subgraphs of uncountably chromatic graphs
复制标题
DOI：
10.1002/jgt.v49:1
复制
发表时间：
2005-05
影响因子：
0.9
通讯作者：
Péter Komjáth;S. Shelah
中科院分区：
文献类型：
--
作者：
Péter Komjáth;S. Shelah
证明了对任意函数f：ω → ω，存在一个图的大小和色数均为n ≥ 1，且每个n-色子图至少包含f（n）个顶点（n ≥ 3）。这解决了鄂尔多斯250美元的问题。相容的是存在图X，其中Chr（X）=| X|如果Y是一个所有有限子图都出现在X中的图，则Chr（Y）≤ λ 2（因此泰勒猜想可能失败）。如果X是一个色数至少为λ 2的图，则对每个基数λ，存在一个图Y，其Chr（Y）λ的有限子图都是X的导出子图，这也是相容的.© 2005 Wiley Periodicals，Inc. J Graph Theory 49：2838，2005
It is consistent that for every function f:ω → ω there is a graph with size and chromatic number ℵ1 in which every n-chromatic subgraph contains at least f(n) vertices (n ≥ 3). This solves a $ 250 problem of Erdos. It is consistent that there is a graph X with Chr(X)=|X|=ℵ1 such that if Y is a graph all whose finite subgraphs occur in X then Chr(Y)≤ℵ2 (so the Taylor conjecture may fail). It is also consistent that if X is a graph with chromatic number at least ℵ2 then for every cardinal λ there exists a graph Y with Chr(Y)λ all whose finite subgraphs are induced subgraphs of X. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 2838, 2005