𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Finite subgraphs of uncountably chromatic graphs

✍ Scribed by Péter Komjáth; Saharon Shelah

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
112 KB
Volume
49
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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 Erdős. 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: 28–38, 2005

📜 SIMILAR VOLUMES

Distance Graphs with Finite Chromatic Nu
Distance Graphs with Finite Chromatic Number
✍ I.Z. Ruzsa; Zs. Tuza; M. Voigt 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 96 KB

The distance graph G(D) with distance set D={d 1 , d 2 , ...} has the set Z of integers as vertex set, with two vertices i, j ¥ Z adjacent if and only if |i -j| ¥ D. We prove that the chromatic number of G(D) is finite whenever inf{d i+1 /d i } > 1 and that every growth speed smaller than this admit

Circular chromatic number of subgraphs
Circular chromatic number of subgraphs
✍ Hossein Hajiabolhassan; Xuding Zhu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB

## Abstract This paper proves that every (__n__ + )‐chromatic graph contains a subgraph __H__ with $\chi \_c (H) = n$. This provides an easy method for constructing sparse graphs __G__ with $\chi\_c (G) = \chi ( G) = n$. It is also proved that for any ε > 0, for any fraction __k/d__ > 2, there exis

Finite Induced Graph Ramsey Theory: On P
Finite Induced Graph Ramsey Theory: On Partitions of Subgraphs
✍ D.S. Gunderson; V. Rodl; N.W. Sauer 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 425 KB

For given finite (unordered) graphs \(G\) and \(H\), we examine the existence of a Ramsey graph \(F\) for which the strong Ramsey arrow \(F \rightarrow(G)_{r}^{\prime \prime}\) holds. We concentrate on the situation when \(H\) is not a complete graph. The set of graphs \(G\) for which there exists a

Chromatic number of finite and infinite
Chromatic number of finite and infinite graphs and hypergraphs
✍ Paul Erdös; Andras Hajnal 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 349 KB

We wrote many papers on these subjects, some in collaboration with Galvin, Rado, Shelah and Szemer6di, and posed many problems some of which turned out to be undecidable. In this survey we state some old and new solved and unsolved problems. Nous avons 6crit beaucoup d'articles, certains en collabo