Borel chromatic number of closed graphs

2014/06/29 by Dominique Lecomte, Lecomte, Dominique, Miroslav Zelený +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #General Topology (math.GN) #Limits and Structures in Graph Theory #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.1406.7544

openalex publication_date 2014/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct, for each countable ordinal ξ, a closed graph with Borel chromatic number two and Baire class ξ chromatic number ℵ_0.

Related

• Descriptive Chromatic Numbers of Locally Finite and Everywhere Two Ended Graphs
• Borel chromatic numbers of closed graphs and forcing with uniform trees
• Ramsey, expanders, and Borel chromatic numbers
• Borel chromatic numbers of locally countable F_σ graphs and forcing with superperfect trees
• The b-Chromatic Number of Certain Graphs and Digraphs