On incompactness for chromatic number of graphs

2012/05/01 by Saharon Shelah, Shelah, Saharon
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #math.CO #math.LO

paper · pdf · doi:10.48550/arxiv.1205.0064

published as Acta Math. Hungar. 139 No. 4 (2013) 363--371

arxiv created 2012/08/06 · arxiv updated 2012/08/08

Abstract

We deal with incompactness. Assume the existence of non-reflecting stationary set of cofinality kappa . We prove that one can define a graph G whose chromatic number is > kappa, while the chromatic number of every subgraph G' subseteq G,|G'| < |G| is <= kappa . The main case is kappa = aleph₀.

Related

• More on Compactness of Chromatic Numbers
• Reflection on the coloring and chromatic numbers
• The list-chromatic number and the coloring number of uncountable graphs
• Finite subgraphs of uncountably chromatic graphs
• A note on uncountably chromatic graphs