Relative independence of the simultaneous chromatic number at ℵ₁
Version 1 / Nov 18, 2026 / CC BY 4.0
Abstract
Let assert that every graph of chromatic number admits an edge coloring with palette such that every countable partition of its vertices has a part whose induced edges realize the whole palette. Hajnal and Komjáth proved the relative consistency of by adding a Cohen real. We prove the relative consistency of from one Woodin cardinal. In the negative model a single graph of chromatic number has the stronger property that every binary edge coloring admits a countable partition into parts with monochromatic induced edges.
Provenance statement
References
- T. F. Bloom, Erdős Problem #1176 , https://www.erdosproblems.com/1176.link
- A. Hajnal and P. Komjáth, Some remarks on the simultaneous chromatic number , Combinatorica 23 (2003), 89--104. doi:10.1007/s00493-003-0015-2 (https://doi.org/10.1007/s00493-003-0015-2).DOI
- S. Hoffelner, NS saturated and -definable , J. Symbolic Logic 86 (2021), 25--59. doi:10.1017/jsl.2021.23 (https://doi.org/10.1017/jsl.2021.23). Theorem numbering follows arXiv:1701.07230v5 (https://arxiv.org/abs/1701.07230v5).arXivDOI
Version history
- v1 · 5 pagesSubmitted by Liam KruerInitial depositCurrentNov 18, 2026