Finite subgraphs of uncountably chromatic graphs

DOI10.1002/JGT.20060MaRDI QIDQ4680402zbMATH OpenOpenAlexFDO

Authors Péter Komjáth, S. Shelah

Publication date 1 June 2005

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0212064

zbMATH Keywords

chromatic numberinfinite graphsTaylor conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $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 (so the Taylor conjecture may fail).

Recommendations

• On Taylor's problem
• scientific article; zbMATH DE number 426350
• scientific article; zbMATH DE number 3468845
• On the growth rate of chromatic numbers of finite subgraphs
• What must and what need not be contained in a graph of uncountable chromatic number?

Cited in

(13)

• The chromatic number of infinite graphs - A survey
• Hajnal-Máté graphs, Cohen reals, and disjoint-type guessing
• Uncountable dichromatic number without short directed cycles
• Consistency results on infinite graphs
• scientific article; zbMATH DE number 3520443 (Why is no real title available?)
• Infinite stable graphs with large chromatic number
• The chromatic number of finite type-graphs
• Coloring finite subsets of uncountable sets
• On the growth rate of dichromatic numbers of finite subdigraphs
• A consistent edge partition theorem for infinite graphs
• On the growth rate of chromatic numbers of finite subgraphs
• Infinitely connected subgraphs in graphs of uncountable chromatic number
• On Taylor's problem

This page was built for publication: Finite subgraphs of uncountably chromatic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4680402)