More on Compactness of Chromatic Numbers

2013/02/14 by Saharon Shelah, Shelah, Saharon
Computer Science · Mathematics · #03E05 #05C15 #Advanced Graph Theory Research #Advanced Topology and Set Theory #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.1302.3431

openalex publication_date 2013/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that for any regular kappa and mu > kappa below the first fix point (lambda = aleph_lambda) above kappa, there is a graph with chromatic number > kappa, and mu^kappa nodes but every subgraph of cardinality < mu has chromatic number less than or equal to kappa.

Related

• List chromatic numbers and singular compactness
• On incompactness for chromatic number of graphs
• Finite subgraphs of uncountably chromatic graphs
• Topological lower bounds for the chromatic number: A hierarchy
• A survey of χ‐boundedness