Finite subgraphs of uncountably chromatic graphs

DOI10.1002/JGT.20060zbMATH Open1064.05058arXivmath/0212064OpenAlexW2950528977MaRDI QIDQ4680402FDOQ4680402

Authors: Péter Komjáth, S. Shelah 

Publication date: 1 June 2005

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

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).

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

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?

zbMATH Keywords

chromatic numberinfinite graphsTaylor conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)

Cited In (12)

• 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
• Infinite stable graphs with large chromatic number
• Title not available (Why is that?)
• Consistency results on infinite graphs
• 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

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)